如何我在Java

Question

B B B B B 

B B B O B 

B B S O B 

B O O B B 

B B X B B 

這裏使用2D陣列迷宮找到路徑，

S =開始點（2,2）

B =塊

O =打開

X =退出

我想製作一個迷宮，它將檢查北部，西部，東部和南部。如果X在附近，它將返回程序。如果不是，則檢查起點周圍的任何「O」並遞歸傳遞新的起點。它沒有辦法去，'X'沒有找到它會回到原始的起點（2,2），並檢查西部，東部和南部。

程序後，我得到：

B B B B B 

B B B + B 

B B + + B 

B O + B B 

B B X B B 

，但是，我希望遞歸後的輸出是：

B B B B B 

B B B - B 

B B + - B 

B O + B B 

B B X B B 

這是我的代碼現在：

public static void Find_Path(char[][] maze, int startX, int startY){ 
int x[] = { -1, 0, 0, 1}; 
int y[] = {0,-1,1,0}; 
boolean found = false; 
maze[startX][startY] = '+'; 
for(int i = 0; i < 4 ; i++){// check if there are 'X' around the S. 
    int afterX = x[i] + startX; 
    int afterY = y[i] + startY; 
    if(maze[afterX][afterY] == 'X'){// if yesy, return. 
    found = true; 
    return; 
    } 
} 

for(int i = 0; i < 4 ; i++){// if no, check for 'O' 
    int afterX = x[i] + startX; 
    int afterY = y[i] + startY; 
    if(maze[afterX][afterY] == 'O'){ 
    Find_Path(maze, afterX, afterY); 
    if(!found){ 
    maze[afterX][afterY] = '-'; 
    } 
} 
} 

startX和startY是起點的索引。

我不知道如何把錯誤的路徑' - '。程序將首先檢查北方如果頂部是B，那麼它會回溯並返回到起點。然後，它將向東，向西和向南。

任何人都可以幫我嗎？謝謝！ @Muntasir

BBBBB 
BBOOB 
XOBOB 
BSOBB 
BBBBB 

BBBBB 
BBOOB 
X+BOB (It should stop right here, because there is X around it.) 
BSOBB 
BBBBB 

BBBBB 
BBOOB 
X+BOB (but, somehow it go to the right of the startpoint and mark the 'O' to '+' 
BS+BB 
BBBBB 

Answer 1

使用全局變量（標誌），以確定是否找到了正確的路徑。

例如：

public class YourClass{ 
    static boolean found = false; // the global flag 
    // your existing code 

    public static void Find_Path(char[][] maze, int startX, int startY){ 
     // .... 
     for(int i = 0; i < 4 ; i++){ 
      // ... 
      if(maze[afterX][afterY] == 'X'){ 
       found = true; // path found 
       return; 
      } 
     } 
     for(int i = 0; i < 4 ; i++){ 
      // ... 
      if(found) // path already found in earlier recursive call; no need to search anymore 
       return; 
      else{ // path not found yet, have to continue searching 
       if(maze[afterX][afterY] == 'O'){ 
        Find_Path(maze, afterX, afterY); 
        if(!found){ // path not found 
         maze[afterX][afterY] = '-'; 
        } 
       } 
      } 
     } 
    } 
} 

Answer 2

你正在尋找被稱爲廣度優先搜索和深度優先搜索的算法。你會遇到的問題是如果你的迷宮中存在一個循環。例如，如果你有這個，會發生什麼？

B B B B B 
B O O O B 
B O S O B 
B O O O B 
B B B B B 

然後，算法可能會卡在一個無法逃脫的循環中。

解決這個問題的經典方法是使用另一個表示頂點是否曾被訪問過的數據結構對頂點進行「着色」。

這MIT OCW的演講可能會幫助你指明正確的方向：https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-13-breadth-first-search-bfs/

直接回答你的問題，不過，想想基地的情況。當你找到X時，什麼能阻止旋轉和旋轉的循環？在目前的狀態下，它看起來像停止迭代/遞歸的唯一的事情就是你沒有足夠的空間去尋找。你需要一些變量來告訴第二個循環停止搜索。

Answer 3

由於提出問題，這個解決方案應該工作：

import java.util.Arrays; 

public class TwoDSolver { 

private char[][] maze; 
private String currPath; 
private int currX; 
private int currY; 
private boolean unsolvable; 

public static void main(String[] args) { 
    char[][] customMaze = { 
      {'B', 'B', 'B', 'B', 'B'}, 
      {'B', 'B', 'B', 'O', 'B'}, 
      {'B', 'B', 'S', 'O', 'B'}, 
      {'B', 'O', 'O', 'B', 'B'}, 
      {'B', 'B', 'X', 'B', 'B'} 
    }; 

    String startPath = ""; 
    int startX = 2; 
    int startY = 2; 
    TwoDSolver solver = new TwoDSolver(customMaze, startX, startY, startPath, false); 
    // place a plus at the start point 
    solver.placePlus(); 
    solver.solveMaze(); 
    if (solver.unsolvable) { 
     System.out.println("The maze is unsolvable"); 
    } else { 
     System.out.println("Solved, A correct path is: " + solver.currPath); 
    } 
    solver.printMaze(); 


} 

// constructor 
TwoDSolver(char[][]aMaze, int stX, int stY, String currentPath, boolean noSolution) { 
    maze = aMaze; 
    currX = stX; 
    currY = stY; 
    currPath = currentPath; 
    unsolvable = noSolution; 
} 

// indicate taken path 
void placePlus() { 
    maze[currX][currY] = '+'; 
} 

// for backtracking 
void placeMinus() { 
    maze[currX][currY] = '-'; 
} 

// solve 
// priority in this order East, West, South, North 
void solveMaze() { 
    // check for a win 
    if (checkForWin()) { 
     return; 
    } 
    // No win, so let's check for an opening 
    // check east 
    if (currY + 1 < maze[currX].length && checkForOpen(currX, currY + 1)) { 
     currY++; 
     placePlus(); 
     currPath += "E"; // Append East to our current path 
     // recursive call continue searching 
     solveMaze(); 
     // check west 
    } else if (currY - 1 >= 0 && checkForOpen(currX, currY - 1)) { 
     currY--; 
     placePlus(); 
     currPath += "W"; 
     solveMaze(); 
     // check south 
    } else if (currX + 1 < maze.length && checkForOpen(currX + 1, currY)) { 
     currX++; 
     placePlus(); 
     currPath += "S"; 
     solveMaze(); 
     // check north 
    } else if (currX - 1 >= 0 && checkForOpen(currX - 1, currY)) { 
     currX--; 
     placePlus(); 
     currPath += "N"; 
     solveMaze(); 
    } else { // we've hit a dead end, we need to backtrack 
     if (currPath.length() == 0) { 
      // we're back at the starting point, the maze is unsolvable 
      unsolvable = true; 
      return; 
     } else { 
      // we've reached a dead end, lets backtrack 
      placeMinus(); 
      backTrack(); 
     } 
    } 
} 

// see if the spot at a give x, y is open 
boolean checkForOpen(int x, int y) { 
    return maze[x][y] == 'O'; 
} 

// see if any of the surrounding spots are the exit 
boolean checkForWin() { 
    // make sure to protect against out of bounds as well 
    return ((currY + 1 < maze[currX].length && maze[currX][currY + 1] == 'X') || 
      (currY - 1 >= 0 && maze[currX][currY - 1] == 'X') || 
      (currX + 1 < maze[currX].length && maze[currX + 1][currY] == 'X') || 
      (currX -1 >= 0 && maze[currX -1][currY] == 'X')); 
} 

void backTrack() { 
    // sanity chek currPath.length() should always be > 0 when we call backTrack 
    if (currPath.length() > 0) { 
     placeMinus(); 
     switch (currPath.charAt(currPath.length() - 1)) { 
     case 'E': 
      currY--; 
      break; 
     case 'W': 
      currY++; 
      break; 
     case 'S': 
      currX--; 
      break; 
     case 'N': 
      currX++; 
      break; 
     } 
     currPath = currPath.substring(0, currPath.length()-1); 
     solveMaze();  
    } 
} 

void printMaze() { 
    for (int i = 0; i < maze.length; i++) { 
     System.out.println(Arrays.toString(maze[i])); 
    } 
} 

} 

對於示例迷宮輸出：

Solved, A correct path is: S 
[B, B, B, B, B] 
[B, B, B, -, B] 
[B, B, +, -, B] 
[B, O, +, B, B] 
[B, B, X, B, B] 

對於由@William霍華德旨意的例子迷宮是無解：

{'B', 'B', 'B', 'B', 'B'}, 
{'B', 'O', 'O', 'O', 'B'}, 
{'B', 'O', 'S', 'O', 'B'}, 
{'B', 'O', 'O', 'O', 'B'}, 
{'B', 'B', 'B', 'B', 'B'} 

的輸出是：

The maze is unsolvable 
[B, B, B, B, B] 
[B, -, -, -, B] 
[B, -, +, -, B] 
[B, -, -, -, B] 
[B, B, B, B, B] 

有一點要注意這個解決方案，並接近問題的思考方式： 這將不會提供給出口

該解決方案順序優先最短路徑：東，西， 南北。

這裏是我的意思的例子：

開始迷宮：

{'B', 'B', 'B', 'X', 'B'}, 
{'B', 'O', 'O', 'O', 'B'}, 
{'B', 'O', 'S', 'O', 'B'}, 
{'B', 'O', 'O', 'O', 'B'}, 
{'B', 'B', 'B', 'B', 'B'} 

輸出：

Solved, A correct path is: ESWWNNEE 
[B, B, B, X, B] 
[B, +, +, +, B] 
[B, +, +, +, B] 
[B, +, +, +, B] 
[B, B, B, B, B] 

正如你可以看到有到出口，NE多個正確的路徑， EN，WNEE，SENN，SWNNEE，ESWWNNEE（這是算法優先選擇的一個）。

我認爲您從發佈的代碼中遺漏的主要內容是一種記錄您當前路徑和回溯的方式，當您遇到死衚衕時。