扫地机器人，Robot API、实现及总结

楼主您好，因为我看到这题的版本是move()返回面前有没有obstacle，所以逻辑应该比你github上的要简单些，大概如下：

对于这题，我们不知道房间的大小，但可以假设robot的起始位置是（0，0），并且面朝方向（1，0）。然后，进行DFS：
     在每一个点上，我们尝试turnLeft() 4次，分别朝四个方向，如果move() return true，并且没有visited过，那么朝这个方向走一格，进行下一层的dfs。
     如果move return false，那么说明是障碍物或者房间边界。
需要加入visited。
     如果遍历完一个点上能走的所有情况，机器人需要手动掉头，走一步，再掉头，回到上一层进入这一层时的状态。

补充内容 (2018-5-2 08:19):
手抖，还没打完就提交了。。。。然后走过所有的点都加入visited。当在一个点上turnLeft四次，又转到进来时的状态时，就掉头，走一步，再掉头，回到进入这个点之前的状态，进行其他的dfs，一直到无处可走，dfs结束

补充内容 (2018-5-2 08:20):
但是作为一道热题，我实现完的代码实在太短了，感觉不像是狗家热题的样子。。。所以还请楼主看看我这思路有没有问题

Avogadro 发表于 2018-5-2 08:17
楼主您好，因为我看到这题的版本是move()返回面前有没有obstacle，所以逻辑应该比你github上的要简单些，大 ...

你好啊，你的想法很棒，我提一个我觉得可能产生的问题。

在你的实现里面，在同一个格子转四次，也就意味着在进入一个格子之后，机器人会先左转，进入下一个格子，再左转，持续这个过程，那么如果在维护相对座标的时候需要很小心，因为在踏入相同的格子的时候很可能会把这个格子视为不同的相对座标，导致死循环。

我觉得你可以直接试一下，一来是我可能出错，二来是我拒绝当 debug 机 (不小心说出了心声 233)。你可以到那份文件 `other/robot_cleaner.py` 里面去改写 `RobotCleanerDFS` 的实现。面试中主要需要回答的也就这部分，文件里的其他代码只是为了模拟机器人 API～

必须顶，找了好久想看个完整的题目和idea，点一万个赞！

tommyttang 发表于 2018-5-2 12:44
必须顶，找了好久想看个完整的题目和idea，点一万个赞！

很高兴你喜欢，祝顺利！

谢谢楼主分享 看了各位的讨论 对这个题的理解更加深入了

dfs1 想和楼主讨论一下：
1. 可不可以这样操作以当前方向进入这个点后， dfs 三个方向， 向前（不变）， 向左（turnleft (1)), 向右（turnright(1)).
2. dfs 后回溯， 向左180度 回到上一个点， (不用查看visited, 或者抹去上一个点的visited)。

楼主的dfs1里面是走了四个方向 并且都判断visited, 这样是不是回不去上一个点呢， 这样如果进入了死胡同， 要怎么走回去呢？

希望楼主解答， 已加米 谢谢！！

seblsb 发表于 2018-5-3 06:40
谢谢楼主分享 看了各位的讨论 对这个题的理解更加深入了

dfs1 想和楼主讨论一下：

dfs1 的实现里面，代码里面有四个方向的 block，但不是四个方向都能踩进去呀。如果从左进去格子，那么就不会再从上右下再进来了，所以这里 visited 就是为了保证只能进每个格子一次，注意这里指的只是进。
至于回，确实就像你讲的，是利用 dfs 出来之后的回溯让 robot 在踏回来这个格子。

可以直接复写 `RobotCleanerDFS` 里面的代码，然后跑 `python -m doctest -v other/robot_cleaner.py` 就能检验你的想法了：）

感谢楼主！学习一下

感谢分享！

艹我以为是技术贴如何自己通过api让我家roomba更聪明呢。。。顺带恭喜一下好了。。。

超级好的帖子，谢谢楼主！