使用左手法则解算迷宫
使用左手法则解算迷宫
提问于 2010-12-06 10:22:05
我正在尝试使用左手退出规则来解决迷宫，使用下面的sudo代码我已经让它大部分工作了，但我有问题让它选择一个新的方向，当它到达死胡同并回来(比如在一个正方形的情况下，它的顶部是真的，但在第一阶段左，底和右墙都是假的，我的代码正确地从例如如果入口是左移动到2个底部或右边中的任何一个，但当它返回时它选择左方向而不是底部，我如何让它选择底部)。
有人可以建议我如何选择新的方向吗?我已经在这个方法周围加上了两个星号(**)，以便提前向你推荐。
Set int entr to LEFT;
Set int exit to-1;
Set boolean backtrack to false;
Set currentSquare to startingSquare;
Set previousSquare to null;
Set currentSquare.onpath to true;
While (currentSquare != endingSquare) {
**Set exit to currentSquare.getLeftHandExit(entr);**
Set previousSquare to currentSquare;
Set currentSquare to currentSquare.adjacentSquare(exit);
If (backtracking is false and exit is same as entrance)
Set backtracking to true;
Remove previousSquare from path;
}
Else if backtracking is true and currentSquare is not on the path
Set backtracking to false;
Add previousSquare to path;
}
If backtracking is true, remove currentSquare from path;
else add currentSquare to path;
entr = currentSquare.oppositeSide(exit);
} // end of WhileStack Overflow用户
发布于 2010-12-06 10:33:05
使用回溯系统；无论是使用递归方法(不可取)还是使用堆栈回溯步骤。理想情况下，您还应该在算法选择路径的每个交叉点设置标记，这样就不会再次选择相同的路径(只选择给定交叉点中未标记的路径)
维基百科有一些关于如何实现这一点的nice pseudocode。注意"Recursive backtracker“算法，将”随机选择一个未访问的邻居“替换为”从一个未访问的邻居中选择左转“(意思是从左边的单元格按时钟方向选择)。
此外，请查看有关递归性的this e-book。
我会选择这样的代码(未测试的代码)：
maze.clearAllVisited();
Stack<Point> paths = new Stack<Point>();
int x = maze.getStartX();
int y = maze.getStartY();
while (!maze.isExit(x, y)) {
maze.setVisited(x, y);
if (maze.canGoWest(x, y)) { // check if west cell is accessible from x,y and has not been visited
paths.push(new Point(x, y));
x--;
} else if (maze.canGoNorth(x, y)) { // check if north cell is accessible from x,y and has not been visited
paths.push(new Point(x, y));
y--;
} else if (maze.canGoEast(x, y)) { // ...
paths.push(new Point(x, y));
x++;
} else if (maze.canGoSouth(x, y)) { // ...
paths.push(new Point(x, y));
y++;
} else {
if (paths.isEmpty()) {
break; // no more path for backtracking, exit (aka no solution for maze)
}
// dead end! go back!
Point last = stack.pop();
x = last.x;
y = last.y;
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/4362657
复制相关文章
相似问题
腾讯云开发者
