扫地机器人，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 里面的东西而已。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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

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

多谢多谢啊，楼主加油

辛苦啦，楼主很厉害

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

thanks so much.

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

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

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