java - 路径寻找迷宫错误

Question

我正在尝试实现深度优先算法来解决迷宫，但我编写的代码不知何故似乎没有做任何事情，既不引发错误，也不产生预期结果，女巫正在“填充”路径具有访问坐标的数组，因为当我打印路径数组时，我得到一个空数组。

public static boolean searchPath(char[][] maze, int x, int y, List<Integer> path) {

    if(maze[y][x]=='E') {
        path.add(x);
        path.add(y);
        return true;
    }
    if(maze[y][x]=='_') {

        int dx = -1;
        int dy = 0;
        if(x +dx >0 && y + dx > 0 && x + dx < maze.length && y + dx < maze[0].length && searchPath(maze,x+dx,y+dy,path)) {
            path.add(x);
            path.add(y);
            return true;
        }

        dx = 1;
        dy = 0;
        if (x +dx >0 && y + dx > 0 && x + dx < maze.length && y + dx < maze[0].length && searchPath(maze, x + dx, y + dy, path)) {
            path.add(x);
            path.add(y);
            return true;
        }

        dx = 0;
        dy = -1;
        if (x +dx >0 && y + dx > 0 && x + dx < maze.length && y + dx < maze[0].length &&  searchPath(maze, x + dx, y + dy, path)) {
            path.add(x);
            path.add(y);
            return true;
        }

        dx = 0;
        dy = 1;
        if (x +dx >0 && y + dx > 0 && x + dx < maze.length && y + dx < maze[0].length && searchPath(maze, x + dx, y + dy, path)) {
            path.add(x);
            path.add(y);
            return true;
        }
    }
    return false;

}

}

这里是我调用 searchPath 的地方。

    public MazeReader() {

        setTitle("Maze");
        setSize(640,480);
        setLocationRelativeTo(null);
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        DepthFirst.searchPath(Maze, 0, 1, path);
        pathIndex = path.size() - 2;

}

这是我正在处理的迷宫:

_SW_____W
_WWW_W_WW
_____W_EW

我认为问题可能在于迷宫所在的先前数组存储的内容未正确导入到 DepthFirst 类中。有什么办法可以解决这个问题吗？

Answer 1

所以首先你永远不会检查开始符号，所以它从一开始就失败了。将其添加到该行

 if(maze[y][x]=='_' || maze[y][x] == 'S') {

下一行有很多问题

if (x +dx >0 && y + dx > 0 && x + dx < maze.length && y + dx < maze[0].length 

应该是 x+dx >=0，因为可以为 0。您正在使用 x 来检查嵌套数组，因此它应该是 x + dx < maze[0].length && y + dy < maze。长度。您多次添加 y + dx 而不是 y + dy。

最后，您需要某种方法来避免多次返回同一坐标。您的方式会导致堆栈溢出，因为搜索将永远在两个坐标之间来回移动。我添加了一个名为 check 的 boolean 数组，其大小与迷宫相同，当检查坐标时将其设置为 true 以避免再次返回该点。

这里一切都在一起了。

 public static void main(String[] args) {
    List<Integer> l = new LinkedList<Integer>();
    char[][] maze = {{'S', '_', '_'},{'W','W','E'}};
    boolean[][] checked = new boolean[2][3];
    searchPath(maze, 0, 0, l, checked);
    System.out.println(l.toString());
}

public static boolean searchPath(char[][] maze, int x, int y, List<Integer> path, boolean checked[][]) {

    if(checked[y][x]){
        return false;
    }
    checked[y][x] = true;

    if(maze[y][x]=='E') {
        path.add(x);
        path.add(y);
        return true;
    }
    if(maze[y][x]=='_' || maze[y][x] == 'S') {

        int dx = -1;
        int dy = 0;
        if(x +dx >=0 && y + dy >= 0 && x + dx < maze[0].length && y + dy < maze.length && searchPath(maze,x+dx,y+dy,path, checked)) {
            path.add(x);
            path.add(y);
            return true;
        }

        dx = 1;
        dy = 0;
        if(x +dx >=0 && y + dy >= 0 && x + dx < maze[0].length && y + dy < maze.length && searchPath(maze,x+dx,y+dy,path, checked)) {
            path.add(x);
            path.add(y);
            return true;
        }

        dx = 0;
        dy = -1;
        if(x +dx >=0 && y + dy >= 0 && x + dx < maze[0].length && y + dy < maze.length && searchPath(maze,x+dx,y+dy,path, checked)) {
            path.add(x);
            path.add(y);
            return true;
        }

        dx = 0;
        dy = 1;
        if(x +dx >=0 && y + dy >= 0 && x + dx < maze[0].length && y + dy < maze.length && searchPath(maze,x+dx,y+dy,path, checked)) {
            path.add(x);
            path.add(y);
            return true;
        }
    }
    return false;
}