(这不是重复的)我们在所有4边都有一个由X包围的2D迷宫,并且也有内部块。
迷宫中的所有这些字符都存储在二维数组中。程序必须找到从开始'S'到目标'G'的路径。为此,一个名为'solve(int row,int col)的布尔方法被使用并且用'S'的行和列索引进行初始化。该算法必须是递归的。它应该返回true,如果它能够找到'G'的路径并且其他方式是错误的。以下是我试图解决这个显示“部分正确结果”的问题。二维迷宫的递归算法?
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)。它显示堆栈溢出错误。原因是因为递归发生在这个状态的2个点之间(不知怎的,就像间接递归一样)。
我该如何解决这个问题。无论如何要让程序向上移动而不是向下移动?改变条件语句的位置不会工作。并且认为一个有多条路径但只有一条导致'G'的位置。如何回到初始位置并尝试另一条路径?提前致谢。
更新:
Here is a Github Repo link to the complete solution of this problem by me.
我会尝试,看看它是否工作。 –
绝对,它现在工作! –