二维迷宫的递归算法？

Question

（这不是一个复制品）我们有一个2D迷宫，四面都有X，还有内部的方块<迷宫的所有这些特征都存储在2D数组中。程序必须找到从开始“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;
}

以下是它解决的输出：

   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

但是当我把“G”向上一步（在6,8）时。它显示stackOverflow错误。原因是递归发生在这个状态的2个点之间（不知何故就像间接递归一样）。

我怎样才能解决这个问题。有没有办法让程序上移而不是下移？不过，改变条件语句的位置是行不通的。想想一个位置，它有不止一条路要走，但只有一条通向“G”。如何回到初始位置并尝试另一条路径？提前谢谢。

更新：

这里有一个Github Repo链接，指向我对这个问题的完整解决方案。

Answer 1

在您当前的代码中，您有可能返回false，而不查看其他连接的位置。

在退出if状态之前，您应该查看其他可能性
此外，还应检查是否已访问该位置，以避免无限递归。

将您的代码更改为：

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;

Answer 2

您可以使用DFS或BFS。DFS是最简单的。您只需进行递归，在所有4/8方向导航，并将该位置（X，Y）标记为已访问。如果是你命中注定的G，返回真，否则继续。

提示：

• 不要使用同一个矩阵来阅读地图并将其标记为已访问，亲吻
• 你必须经常检查你是否已经发现了G。你可以通过返回FALSE或TRUE，或者你可以使用一个全局html" target="_blank">变量

如果您在实现它时遇到困难，请尝试在谷歌上搜索有关此问题的源代码：http://en.wikipedia.org/wiki/Flood_fill

http://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/

Answer 3

你可以在你已经跨过的空间中填充一个替代符号，这样你的程序就会知道它已经在那里了。