-4

问题：给定一个迷宫作为输入以及入口和出口点，找出是否存在从入口点到出口点的路径。进入迷宫char[][]时，每个值都是“+”或“”（即空格）。A'+'表示一堵墙，其中空间表示它们是一种前进的方式。请注意，我们在任何点的可能移动仅限于 4 个方向，即不允许对角线移动。一个示例迷宫看起来像 {

{'+','+','+','+','+','+','+','+','+','+','+'},
{'+',' ',' ',' ',' ','+',' ','+',' ',' ',' '},
{'+',' ','+',' ','+','+',' ',' ',' ','+','+'},
{'+',' ','+',' ',' ',' ',' ','+',' ','+','+'},
{'+',' ',' ',' ','+','+',' ','+',' ',' ','+'},
{'+','+',' ','+','+','+','+','+','+','+','+'}};

如果入口点是{5,2}，出口点是{1,10}，它们作为输入提供"5:2,1:10"。

问题是：即使路径不存在，此代码也会返回 true。这有什么问题？

例如，它也为这个迷宫返回 true 以及 input 10:7,1:10：

{
{'+','+','+','+','+','+','+','+','+','+','+'};
{'+',' ',' ',' ',' ',' ',' ',' ',' ','+',' '};
{'+',' ','+',' ','+','+',' ','+',' ','+','+'};
{'+',' ','+',' ',' ',' ',' ','+',' ','+','+'};
{'+','+','+',' ','+','+',' ','+',' ',' ','+'};
{'+',' ',' ',' ','+','+',' ',' ',' ',' ','+'};
{'+','+','+','+','+','+','+','+','+',' ','+'};
{'+',' ',' ',' ','+','+',' ',' ','+',' ','+'};
{'+',' ','+','+',' ',' ','+',' ',' ',' ','+'};
{'+',' ',' ',' ',' ',' ','+',' ','+','+','+'};
{'+','+','+','+','+','+','+',' ','+','+','+'}}

这是代码

public class MazePath {

    static char[][] testcase11 = {
{'+','+','+','+','+','+','+','+','+','+','+'};
{'+',' ',' ',' ',' ',' ',' ',' ',' ','+',' '};
{'+',' ','+',' ','+','+',' ','+',' ','+','+'};
{'+',' ','+',' ',' ',' ',' ','+',' ','+','+'};
{'+','+','+',' ','+','+',' ','+',' ',' ','+'};
{'+',' ',' ',' ','+','+',' ',' ',' ',' ','+'};
{'+','+','+','+','+','+','+','+','+',' ','+'};
{'+',' ',' ',' ','+','+',' ',' ','+',' ','+'};
{'+',' ','+','+',' ',' ','+',' ',' ',' ','+'};
{'+',' ',' ',' ',' ',' ','+',' ','+','+','+'};
{'+','+','+','+','+','+','+',' ','+','+','+'}}

    static String testcase12 = "10:7,1:10";

    // Getting start and end points from testcase12
    String[] parts1 = testcase12.split(":");
    String[] parts2 = parts1[1].split(",");

    int startX = Integer.valueOf(parts1[0]);
    int startY = Integer.valueOf(parts2[0]);

    int endX = Integer.valueOf(parts2[1]);
    int endY = Integer.valueOf(parts1[2]);

    static char [][] maze = testcase11;
    int[][] visited;
    int row, col;
    char d; 
    int result;

    public static void main(String[] args) {        
            MazePath testInstance = new MazePath();
            boolean result = testInstance.findPath(testcase11);
            System.out.print("Result is "+result);      
    }

    public boolean findPath(char[][] m)
    {
        row = maze.length;
        col = maze[0].length;

        visited = new int[row][col];
        d = 'o';
        result = 0;

        //System.out.println("Enter maze elements row wise, don't give extra characters (just '+' or ' ' without any ',' or ';')");

        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col ;j++)
            {
                if(maze[i][j] == '+')
                    maze[i][j] = 1;
                else if((maze[i][j] == ' '))
                    maze[i][j] = 0;
                visited[i][j] = -5;
            }
        }

        // 5 means visited, -5 means not visited
        visited[startX][startY] = 5;

        path(startX, startY, d);
        if(result == 0)
            return false;
        else
            return true;

    }

    public int path(int startX, int startY, char d)
    {
        if(d != 'd' && startX - 1 >= 0)
        {
            if(startX - 1 == endX && startY == endY)
            {
                result = 1;
                return 1;
            }
            else if(maze[startX - 1][startY] == 0)
            {
                if(visited[startX-1][startY] == -5)
                {
                    visited[startX-1][startY] = 5;
                    d = 'u';
                    path(startX-1, startY, d);
                }
            }
        }
        if(d != 'u' && startX + 1 <= row)
        {
            if(startX + 1 == endX && startY == endY)
            {
                result = 1;
                return 1;
            }
            if(maze[startX+1][startY] == 0)
            {
                if(visited[startX+1][startY] == -5)
                {
                    visited[startX+1][startY]=5;
                    d = 'd';
                    path(startX+1, startY, d);
                }
            }
        }
        if(d != 'r' && startY-1 >= 0)
        {
            if(startX == endX && startY-1 == endY)
            {
                result=1;
                return 1;
            }
            if(maze[startX][startY-1]==0)
            {
                if(visited[startX][startY-1]==-5)
                {
                    visited[startX][startY-1] = 5;
                    d = 'l';
                    path(startX,startY-1,d);
                }
            }
        }
        if(d != 'l' && startY+1 <= col)
        {
            if(startX == endX && startY+1 == endY)
            {
                result=1;
                return 1;
            }
            if(maze[startX][startY+1] == 0)
            {
                if(visited[startX][startY+1] == -5)
                {
                    visited[startX][startY+1] = 5;
                    d = 'r';
                    path(startX, startY+1, d);
                }
            }
        }
        return 0;
    }
}
4

1 回答 1

0 
Improvised version of your code.

    public class MazePath {

    static char[][] testcase11 = {
        {'+','+','+','+','+','+','+','+','+','+','+'},
        {'+',' ',' ',' ',' ',' ',' ',' ',' ','+',' '},
        {'+',' ','+',' ','+','+',' ','+',' ','+','+'},
        {'+',' ','+',' ',' ',' ',' ','+',' ','+','+'},
        {'+','+','+',' ','+','+',' ','+',' ',' ','+'},
        {'+',' ',' ',' ','+','+',' ',' ',' ',' ','+'},
        {'+','+','+','+','+','+','+','+','+',' ','+'},
        {'+',' ',' ',' ','+','+',' ',' ','+',' ','+'},
        {'+',' ','+','+',' ',' ','+',' ',' ',' ','+'},
        {'+',' ',' ',' ',' ',' ','+',' ','+','+','+'},
        {'+','+','+','+','+','+','+',' ','+','+','+'}};
    static String testcase12 = "10:7,1:10";

    public static void main(String[] args) {        
        MazePath testInstance = new MazePath();
        boolean result = testInstance.findPath(testcase11,testcase12);
        System.out.print("Result is "+result);      
    }   

    public boolean findPath(char[][] maze, String points)
    {
        char [][] inputMaze = maze;

        int row = maze.length;
        int col = maze[0].length;

        // Getting start and end points
        String[] parts1 = points.split(":");
        String[] parts2 = parts1[1].split(",");

        int startX = Integer.valueOf(parts1[0]);
        int startY = Integer.valueOf(parts2[0]);

        int endX = Integer.valueOf(parts2[1]);
        int endY = Integer.valueOf(parts1[2]);

        char[][] visited = new char[row][col];      

        boolean result = path(inputMaze, startX, startY, endX, endY, visited);
        if(!result)
            return false;
        else
            return true;
    }


    public boolean path(char[][] inputMaze,int startX, int startY, int endX, int endY, char[][] visited)
    {
        if((startX == endX) && (startY == endY))
        {
            return true;
        }
        if((startX > inputMaze.length-1) || (startY > inputMaze[0].length-1) && (startX < 0 || startY < 0))
        {
            return false;
        }
        if((inputMaze[startX][startY] == ' ') && (visited[startX][startY] != '*'))
        {
            visited[startX][startY] = '*';
        }
        else
        {
            return false;
        }
        boolean u = path(inputMaze, startX-1, startY, endX, endY, visited);
        boolean d = path(inputMaze, startX+1, startY, endX, endY, visited);
        boolean r = path(inputMaze, startX, startY+1, endX, endY, visited);
        boolean l = path(inputMaze, startX, startY-1, endX, endY, visited);

        return u || d|| l || r;
    }   
}
于 2013-08-29T18:23:23.623 回答