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
这里
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
使用全局变量(标志)来确定是否找到了正确的路径。
例如：
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] = '-';
}
}
}
}
}
}
您正在寻找的算法称为广度优先搜索和深度优先搜索。您将遇到的一个问题是迷宫中是否存在循环。例如，如果你有这个会发生什么？
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
然后算法可能会陷入您无法逃脱的循环中。
解决此问题的经典方法是使用另一种表示以前是否访问过顶点的数据结构来"着色"顶点。
麻省理工学院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 时，是什么阻止了循环翻腾和转动？在当前状态下，看起来停止迭代/递归的唯一方法是您没有地方可以查看。你需要某种变量来告诉第二个 for 循环停止搜索。
当问题被问到时，这个解决方案应该有效：
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(此算法由于方向优先级而选择的路径)。
我认为您发布的代码中缺少的主要内容是一种跟踪当前路径并在遇到死胡同时回溯的方法。