破解编码面试第6版，8.2
破解编码面试第6版，8.2
提问于 2015-09-22 05:08:36
问题状态：“想象一个机器人坐在网格的左上角，有r行和c列。机器人只能向右和向下两个方向移动，但某些单元是”禁区“，因此机器人不能踩到它们。设计一个算法，为机器人找到一条从左上角到右下角的路径。”
我的解决方案是这样做：
while grid[r-1, c] !=null && grid[r-1][c] !=false
{
moveRobotDown();
}
while grid[r, c-1] !=null && grid[r][c-1] !=false
{
moveRobotRight();
}-在两个while循环之后，我将抛出一个使用新的r，c坐标的函数的递归调用。
这似乎是一个非常简单的实现，但答案有一个相当冗长和复杂的解决方案。谁能给我解释一下为什么我的不能用？
回答 3
Stack Overflow用户
发布于 2015-09-22 05:13:16
如果你有一个像这样的‘地图’(其中|是路径，*是机器人结束的地方)，它就不会工作。
|
|
|
*X
XX“机器人”会尽可能向下移动，然后就不能正确移动，你的算法就会失败。
我建议阅读有关树遍历的知识，尤其是A*。
Stack Overflow用户
发布于 2017-04-16 02:35:41
很简单。大约10行代码，时间与行x列成比例。
定义:如果一个单元格可以到达它的右下角，那么它就是“好”的。在第一次传递中，您将确定所有正常的单元格。只需从上到下检查行，从右到左检查每行的列:如果单元格不是“禁区”，或者它位于单元格的右下角，或者位于单元格的上方或左侧，则该单元格没有问题。
如果左上角不好，那么有一个解决方案。否则，从左上角开始。只要你还没有到达右下角，在每个转弯处，你要么向下走，要么向右转到一个可以接受的单元格。
Stack Overflow用户
发布于 2019-05-02 01:32:55
尝试使用bfs或dfs。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/32704600
复制相关文章
相似问题
腾讯云开发者
