如何我在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（这是算法优先选择的一个）。

我认为您从发布的代码中遗漏的主要内容是一种记录您当前路径和回溯的方式，当您遇到死胡同时。