二维迷宫的递归算法？

Question

(这不是重复)我们在所有4个侧面都有一个由X围绕的2D迷宫,也有内部块.
迷宫的所有这些字符都存储在2D数组中.程序必须找到从"S"开始到目标"G"的路径.为此,使用名为'solve(int row,int col)的布尔方法,并使用'S'的行和列索引进行初始化.算法必须是递归的.如果它能够找到'G'的路径并且其他方面是假的,那么它应该返回true.这是我试图解决这个显示"部分正确结果"的问题的方法.

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

您可以在已经介入的空间中填写备用符号,这样您的程序就会知道它已经存在.