java:使用回溯卡在循环中的迷宫解算器
我想通过回溯来解决迷宫,在谷歌搜索之后!我看到这个算法: Recursion: Solving a Maze
这是:
查找路径(x,y)
如果(迷宫外的x,y)返回false
如果(x,y是目标)返回true
如果(x,y未打开)返回false
将x、y标记为解决方案路径的一部分
如果(查找路径(x,y以北)=true)返回true
if(查找路径(x,y以东)=true)返回true
if(查找路径(x,y以南)==true)返回true
if(查找路径(x,y以西)=true)返回true
取消将x、y标记为解决方案路径的一部分
返回false
我尝试正确地实施它,如下所示:
public class main {
public static void main(String[] args) {
// A as a Start and B is finish Line
char maze[][] = {
{ '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' },
{ '#', 'A', ' ', ' ', '#', ' ', '#', ' ', ' ', '#' },
{ '#', ' ', ' ', ' ', '#', ' ', '#', ' ', '#', '#' },
{ '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#' },
{ '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#' },
{ '#', '#', '#', ' ', ' ', ' ', ' ', ' ', ' ', '#' },
{ '#', ' ', ' ', ' ', ' ', '#', '#', '#', '#', '#' },
{ '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', '#', '#' },
{ '#', 'B', '#', ' ', ' ', ' ', ' ', ' ', ' ', '#' },
{ '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' }
};
for (int i = 0; i < maze.length; i++) {
System.out.println(maze[i]);
}
mazeTraversal(maze, 1, 1);
}
static boolean mazeTraversal(char m[][], int i, int j) {
if (m[i][j] == '#')
return false;
if (m[i][j] == 'B')
return true;
// marking as a part of path
m[i][j] = '*';
//north
if ((mazeTraversal(m, i , j - 1)) == true) {
return true;
}
//east
if ((mazeTraversal(m, i + 1 , j)) == true) {
return true;
}
//south
if ((mazeTraversal(m, i , j + 1)) == true) {
return true;
}
//west
if ((mazeTraversal(m, i - 1, j)) == true) {
return true;
}
m[i][j] = ' ';
return false;
}
}
这里是控制台错误:(堆栈溢出)
Exception in thread "main" java.lang.StackOverflowError
at main.mazeTraversal(main.java:35)
at main.mazeTraversal(main.java:35)
at main.mazeTraversal(main.java:43)
at main.mazeTraversal(main.java:35)
at main.mazeTraversal(main.java:43)
at main.mazeTraversal(main.java:35)
at main.mazeTraversal(main.java:43)
at main.mazeTraversal(main.java:35)
at main.mazeTraversal(main.java:43)
at main.mazeTraversal(main.java:35)
at main.mazeTraversal(main.java:43)
at main.mazeTraversal(main.java:35)
at main.mazeTraversal(main.java:43)
at main.mazeTraversal(main.java:35)
at main.mazeTraversal(main.java:43)
at main.mazeTraversal(main.java:35)
我也做过几次跟踪,我看到它卡在一个循环中,再也无法继续下去。。。 是我的代码错了还是算法错了
# 1 楼答案
你进入了一个无限循环。您应该检查您是否返回到已经是路径一部分的单元格中:
# 2 楼答案
开放正方形是不包含
#
或*
的正方形,您只检查#
*
检查不需要以无限递归结束(即返回与刚才相同的方式)将代码更改为
。。。运行解算器后打印结果
。。。这看起来像你要做的