路径寻找迷宫错误

Question

我想实现深度优先算法来解决迷宫，但我写的代码 似乎没有做任何事情，既不会产生错误，也不会产生预期的结果，女巫是“填充”路径 数组与访问coordenates，因为当我打印路径数组我得到一个空数组。

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; 

} 

}

这里就是我所说的搜索路径。

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 

我认为这个问题可以这样的事实奠定了previuos数组，其中迷宫 存储没有被正确地导入到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 <迷宫[0] .length & & y + dy < maze.length。您几次添加y + dx而不是y + dy。

最后，你需要一些方法来避免多次回到同一个坐标。你有它的方式导致堆栈溢出，因为搜索将永远在两个坐标之间来回移动。我添加了一个名为checked的布尔数组，其大小与迷宫的大小相同，当检查坐标时避免再次返回该点。

这里一起。

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; 
}