路徑尋找迷宮錯誤

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