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

楼主在职跳槽，准备期间在地里获得许多帮助，现在已经顺利上岸 F 家。准备过程中碰到很多有意思的题目，想说陆续把一些总结发回来回馈地里，顺便攒点人品。这里面没有扣米的操作，但如果你觉得获得帮助，也可以做两件事情给楼主一些正反馈，1) 为这篇总结加米
2) 为这篇总结的代码所在 repo 加 star (https://github.com/jaychsu/algorithm)。
这篇总结是关于某狗的热题，扫地机器人。但我没在面他家的时候碰到，所以从找到的面经上来看，题目如下：

Given a robot cleaner in a room modeled as a grid.
Each cell in the grid can be empty or blocked.
The robot cleaner with 4 given APIs can move forward, turn left or turn right.
When it tries to move into a blocked cell,
its bumper sensor detects the obstacle and it stays on the current cell.

The 4 APIs are:
clean(): clean the current location.
turnleft(k=1): turn left k*90 degrees.
turnrigt(k=1): turn right k*90 degrees.
move(direction=None): move forward for 1 position, return False if that’s not possible.

其中关于 `move` 这个 API 看到两个版本：一个是没有 parameter，每次就朝机器人面向的方向前进一步，所以需要自己在递归中维护方向；一个是可以传 direction 进去，让机器人直接朝那个方向走一步。

两个版本试下来都能实现，但第一个版本难一些，所以我估计第二个版本应该是第一个版本做不出来的时候，面试官用来降低难度的版本吧。

以下分成三个部分，

• API, Robot and Room
• DFS + 手动维护方向
• DFS + move 可传参方向
  

代码可以在 https://github.com/jaychsu/algorithm/blob/master/other/robot_cleaner.py 看到，这里着重总结，代码就只放连结了。
代码的正确性可以在 repo 的根目录透过这条命令检查 `python -m doctest -v other/robot_cleaner.py`
测试的代码在注释中，以 `>>>` 和 `...` 开头


1. API, Robot and Room
代码：L159-L299，https://github.com/jaychsu/algorithm/blob/master/other/robot_cleaner.py#L159-L299

实现肯定有很多种，但我倾向把 Room 和 Robot 解耦。因为其实做到后来你会发现，Robot 根本不需要知道他在 Room 的实际座标，也不需要知道在 Room 的相对方位，在搜索的过程中维护一套相对的就行（我觉得还挺 make sense 的，毕竟我们在路上走也不需要知道实际经纬度和实际方位）。

Room 负责记录实际的座标和 robot 的所在座标，用来判断 robot 是否撞墙，以及房间是不是已经干净，简单来说这个 API 有上帝视角。
Robot 只记录 robot 面向的方向，以及跟 Room 说我要朝这个方向走，由 Room 返回有没有撞墙。
具体实现其实不难，我只稍微提一下方位，和面经里的分享一样，我用了 0, 1, 2, 3 来代替方位，这样做的好处是要转换方位只需要 `(i + k) % 4` 就行。python 里面能直接 `(i - k) % 4`，也可以直接 `(i - k + 4) % 4` 先换成正数。


2. DFS + 手动维护方向
代码：L325-L371，https://github.com/jaychsu/algorithm/blob/master/other/robot_cleaner.py#L325-L371

手动维护方向稍微 tricky 一些，可以对照代码仔细思考以下这三句话。
- 进格子：举个实例吧，假设当前位于 O 格子，上下左右分别为 UDLR，那么我要往周围移动的方向要顺着 DFS 的特点，D -> R -> L -> U（只要是十字形的移动就行，使得能够尽可能的直走，以及递归退回来的时候能面向进来时候的反向，比如 R -> U -> D -> L 也行）。
- 换方向：比如以下代码，是对应前一步进格子的 D，也就是往下走的部分 (在 robot_cleaner.py 的 L334-L338)

1. # down

复制代码

大白话就是，如果下方 (D) 没去过，而且没墙，就去 (DFS)，回来之后 (机器人面向上方) 转右边进去右方 (R)；如果不能去下方，那么 (机器人面向下方) 转左边进去右方。
- 出格子：要让递归返回的时候，Robot 刚好朝向进去格子的反方向(用前述十字形的移动)，如此才能在递归完准备离开当前格子的时候调用 robot.move() 离开。


3. DFS + move 可传参方向
代码：L393-L417，https://github.com/jaychsu/algorithm/blob/master/other/robot_cleaner.py#L393-L417

没前面那么复杂，中心思想就两个。1) 如果能走，就直接过去 2) 如果走到一个走过的格子，就退回去，然后转回原来的方向


这道题主要就这几个点，希望这篇总结能给现在还在奋战的朋友带来点帮助 :)

如果反馈好的话，下一篇预计会再分享狗家的另一道热题：在 grid 中从左上角走到右上角，以及总结现在看到的四个 followup，1) dp 从 2D 转 1D，2) 必须经过某三个点，3) 是否存在经过某三个点的路径，4) 必须越过某个下界 H。
谢谢大家，祝大家 Offer 拿到手软 :D






补充内容 (2018-4-20 00:37):
换方向那段的代码貌似没贴好，补充在这：
```
if (_x, _y) not in visited and robot.move():
    self.dfs(_x, _y, d, robot, visited)
    robot.turnrigt()
else:
    robot.turnleft()
```

补充内容 (2018-5-5 01:22):
做点补充⋯⋯
文件里面大部分的代码都是为了模拟机器人 API，也有一些测试代码用来保证代码确实能跑。应付面试的话，主要也就答 RobotCleanerDFS 里面的东西而已。

vegito2002 发表于 2018-4-23 11:56
楼主很强, 感谢分享, 已加米;

一个小问题, 为什么DFS用的是PostOrder, 有什么讲究吗?

好问题，我现在还在尝试另外两种实现，1) preorder 和 2) BFS，我分享一下到目前的思路

preorder 非常非常容易 stack overflow，原因是搜索过程中的座标都是相对的，完全不知道实际的座标。所以非常可能兜圈子（也就是所谓的路痴⋯⋯233）
比方说四个格子的实际座标是 (0, 0) => (1, 0) => (1, 1) => (0, 1)，一开始会把 (0, 0) 加入 visited，如果方向维护的不对的话，之后从 (0, 1) 找下一格的时候，可能会错误的把 (0, 0) 标记成不同的相对座标，导致兜圈子
可以尝试一下，但进去下一层之前的换方向需要非常小心

第二个 approach 是 BFS，但因为 robot 的移动必须是在连续的格子之间，所以最直觉的那种肯定是行不通的。需要先想好 robot 的移动策略，比如说先往最上最左移动，找到参考点，同时路上搜集一些可以访问的格子，之后再回来访问这些格子，现在有做出来一版，但看起来太蠢了所以没放上去

建议可以动手实现一下，这里面细节太多了

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

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

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

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

感谢楼主！非常有用啊这篇！

楼主写得很赞，已加米，等级所限，只能加这么多了。期待楼主下一篇大作！

多谢多谢啊，楼主加油

辛苦啦，楼主很厉害

谢谢哈，然而来点实际的啊⋯⋯求加星求加米

thanks so much.

太有用了，感谢楼主，已加米

heeshul 发表于 2018-4-20 09:25
太有用了，感谢楼主，已加米

就喜欢这种简单粗暴的感谢，祝顺利！