Java 二维迷宫的递归算法？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/20187547/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Recursive Algorithm for 2D maze?
提问by Prashant Ghimire
(This is not a duplicate) We have a 2D maze surrounded by X on all 4 sides and there are inner blocks too.
All these characters of the maze is stored in 2D array. The program must find the path from start 'S' to goal 'G'. For this, a boolean method called 'solve(int row, int col) is uses and is initialized with row and column index of 'S'. The algorithm must be recursive. It should return true if its able to find the path to 'G' and false other wise. Here's how I tried to approach this problem which shows "partial correct result".
（这不是重复的）我们有一个 2D 迷宫，四个边都被 X 包围，并且也有内部块。
迷宫的所有这些字符都存储在二维数组中。程序必须找到从起点“S”到目标“G”的路径。为此，使用名为“solve(int row, int col)”的布尔方法并使用“S”的行和列索引进行初始化。该算法必须是递归的。如果它能够找到通往'G'的路径，它应该返回true，否则返回false。这是我尝试解决这个显示“部分正确结果”的问题的方法。
public boolean solve(int row, int col) {
char right = this.theMaze[row][col + 1];
char left = this.theMaze[row][col - 1];
char up = this.theMaze[row - 1][col];
char down = this.theMaze[row + 1][col];
if (right == 'G' || left == 'G' || up == 'G' || down == 'G') {
return true;
}
System.out.println("position=>"+"("+row + ":" + col+")");
if (right == ' ') {
return solve(row,col+1);
}
if (down == ' ') {
return solve(row+1,col);
}
if (left == ' ') {
return solve(row,col-1);
}
if (up == ' ') {
return solve(row-1,col);
}
return false;
}
Here is the output it solved :
这是它解决的输出：
0 1 2 3 4 5 6 7 8 9 10
0 X X X X X X X X X X X
1 X X S X X X X X X X
2 X X X X X X X X X
3 X X X X X X X X X
4 X X X X X X X X X
5 X X X X X X X X X
6 X X X X X X X X X
7 X X X X X X X G X X
8 X X X X
9 X X X X X X X X X X X
position=>(1:2)
position=>(2:2)
position=>(3:2)
position=>(4:2)
position=>(5:2)
position=>(6:2)
position=>(7:2)
position=>(8:2)
position=>(8:3)
position=>(8:4)
position=>(8:5)
position=>(8:6)
position=>(8:7)
true
But when I place 'G' one step up (at 6,8). It shows stackOverflow error. The reason is because the recursion occurs between 2 points at this state (somehow just like indirect recursion).
但是当我将“G”向上放置一步时（在 6,8）。它显示 stackOverflow 错误。原因是因为递归发生在这个状态的 2 个点之间（某种程度上就像间接递归）。
How can I solve this problem. Is there anyway to tell the program to move up instead of down? Changing the position of conditional statements wont work though. And think a position that has more than one path to go but only one leads to 'G'. How to come back to initial position and try anther path ? Thanks in advance.
我怎么解决这个问题。无论如何要告诉程序向上移动而不是向下移动？但是，更改条件语句的位置不起作用。想想一个有不止一条路要走但只有一条通向“G”的位置。如何回到初始位置并尝试花药路径？提前致谢。
Update:
更新：
Here is a Github Repo link to the complete solution of this problem by me.
回答by Abhishek Bansal
In your present code there is a possibility that you return out falsewithout looking at other connected positions.
在您当前的代码中，您有可能在false不查看其他连接位置的情况下返回。
You should look through other possibilities before returning out from the ifcondition.
Also, you should check whether the position has been visited to avoid infinite recursion.
在从if条件中返回之前，您应该查看其他可能性。
此外，您应该检查该位置是否已被访问以避免无限递归。
Change your code to:
将您的代码更改为：
bool solved = false;
visited[row][col] = true;
if (right == ' ' && !visited[row][col+1]) {
solved = solve(row,col+1);
}
if (down == ' ' && !solved && !visited[row+1][col]) {
solved = solve(row+1,col);
}
if (left == ' ' && !solved && !visited[row][col-1]) {
solved = solve(row,col-1);
}
if (up == ' ' && !solved !visited[row-1][col]) {
solved = solve(row-1,col);
}
return solved;
回答by Michael Krejci
You could fill in an alternate symbol in the spaces you stepped through already so your program will know that it was there already.
您可以在已经跨过的空间中填写一个替代符号，这样您的程序就会知道它已经存在了。
回答by Mário
You can use a DFS or BFS. The DFS is the easiest one. You simply make a recursion, navigate in all 4/8-directions and mark that place (X,Y) as visited. If it's you destiny 'G', return true otherwise continue.
您可以使用 DFS 或 BFS。DFS 是最简单的一种。您只需进行递归，在所有 4/8 方向上导航并将该位置 (X,Y) 标记为已访问。如果是你的命运'G'，返回真否则继续。
Tips:
提示：
- Don't use the same matrix to read the map and mark it as visited, KISS
- You have to constantly check if you have discovered G. You can make this by return always FALSE or TRUE, or you can use a global variable.
- 不要使用相同的矩阵读取地图并将其标记为已访问，KISS
- 您必须不断检查是否发现了 G。您可以通过始终返回 FALSE 或 TRUE 来实现这一点，或者您可以使用全局变量。
If you have trouble implementing it try to google for some source code about this problems: http://en.wikipedia.org/wiki/Flood_fill
如果您在实现它时遇到问题，请尝试使用谷歌搜索有关此问题的一些源代码：http: //en.wikipedia.org/wiki/Flood_fill
http://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/
http://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/
回答by Vikram Bhat
Here is a pseudo code for you to solve the maze and also retrace the solution : -
这是一个伪代码，供您解决迷宫并回溯解决方案：-
boolean Solve(int x,int y) {
if(isTarget(x,y))
return(true)
if(valid(x+1,y)&&Map[x+1][y]==' ') {
Map[x][y] = 'D'
if(Solve(x+1,y))
return(true)
Map[x][y] = ' '
}
if(valid(x-1,y)&&Map[x-1][y]==' ') {
Map[x][y] = 'U'
if(Solve(x-1,y))
return(true)
Map[x][y] = ' '
}
if(valid(x,y+1)&&Map[x][y+1]==' ') {
Map[x][y] = 'R'
if(Solve(x,y+1))
return(true)
Map[x][y] = ' '
}
if(valid(x,y-1)&&Map[x][y-1]==' ') {
Map[x][y] = 'L'
if(Solve(x,y-1))
return(true)
Map[x][y] = ' '
}
return(false);
}
回答by Prashant Ghimire
Incase you are looking for the complete solution, I have uploaded it on my Github Repository.
如果您正在寻找完整的解决方案，我已将其上传到我的Github 存储库。
回答by Rohit
Inspired by this article Solving a 2D Maze, a recursive solution
灵感来自这篇文章Solving a 2D Maze，一个递归的解决方案
const CORRIDOR = 0;
const WALL = 1;
const EXIT = 2;
// board - 2D array
// start - [row, column] location of start point
function findPath(board, start) {
let seenPath = new Set();
findPathRecur(board, start, seenPath)
return Array.from(seenPath);
}
function findPathRecur(board, point, seenPath) {
let row = point[0],
column = point[1];
// Base Case
if (!isValidPathPoint(board, point, seenPath)) {
return false;
}
if (board[row][column] === EXIT) {
seenPath.add(point.toString());
return true;
}
// console.log("Curr -", point, ", Seen -", Array.from(seenPath));
seenPath.add(point.toString());
let leftColumn = [row, column - 1],
rightColumn = [row, column + 1],
topRow = [row - 1, column],
bottomRow = [row + 1, column];
if (findPathRecur(board, leftColumn, seenPath)) {
return true;
}
if (findPathRecur(board, rightColumn, seenPath)) {
return true;
}
if (findPathRecur(board, topRow, seenPath)) {
return true;
}
if (findPathRecur(board, bottomRow, seenPath)) {
return true;
}
seenPath.delete(point.toString());
return false;
}
// Check if the point is on valid path
function isValidPathPoint(board, point, seenPath) {
let row = point[0];
let column = point[1];
// Check if point exists
if (board[row] != null && board[row][column] != null) {
// To avoid cycle
if (!seenPath.has(point.toString())) {
// Not a Wall
if (board[row][column] !== WALL) {
return true;
}
}
}
return false;
}
// Test Program
let maze = [
[1, 1, 1],
[0, 0, 1],
[1, 2, 1]
];
let testStart = [
[1,0],
[1,1],
[2,1],
[0,0],
[5,5]
];
testStart.forEach(function(start, i) {
console.log("Test Case:",i);
console.log("\tStart -", start, "Path -", findPath(maze, start));
})