LeetCode刷题实战489：扫地机器人-轻识

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 扫地机器人，我们先来看题面：

https://leetcode-cn.com/problems/robot-room-cleaner/

示例

输入:
room = [
  [1,1,1,1,1,0,1,1],
  [1,1,1,1,1,0,1,1],
  [1,0,1,1,1,1,1,1],
  [0,0,0,1,0,0,0,0],
  [1,1,1,1,1,1,1,1]
],
row = 1,
col = 3
解析:
房间格栅用0或1填充。0表示障碍物，1表示可以通过。
机器人从row=1，col=3的初始位置出发。在左上角的一行以下，三列以右。

解题

http://www.javashuo.com/article/p-yvxgcwal-mq.html

给了咱们一个扫地机器人，给了4个 API 函数可供咱们调用，具体实现不用咱们操心，让咱们实现打扫房间 cleanRoom 函数。给的例子中有房间和起始位置的信息，可是代码中却没有，摆明是不想让咱们被分心。想一想也是，难道咱们在给扫地机器人编程时，还必需要知道用户的房间信息么？

固然不可以啦，题目中也说了让咱们盲目 Blindfolded 一些，因此就盲目的写吧。既然是扫地，那么确定要记录哪些位置已经扫过了，因此确定要记录位置信息，因为不知道全局位置，那么只能用相对位置信息了。初始时就是 (0, 0)，而后上下左右加1减1便可。位置信息就放在一个 HashSet 中就能够了，同时为了方便，还能够将二维坐标编码成一个字符串。

咱们采用递归 DFS 来作，初始化位置为 (0, 0)，而后建一个上下左右的方向数组，使用一个变量 dir 来从中取数。在递归函数中，咱们首先对起始位置调用 clean 函数，由于题目中说了起始位置是能到达的，便是为1的地方。而后就要把起始位置加入 visited。而后咱们循环四次，由于有四个方向，因为递归函数传进来的 dir 是上一次转到的方向，那么此时咱们 dir 加上i，为了防止越界，对4取余，就是咱们新的方向了，而后算出新的位置坐标 newX 和 newY。此时先要判断 visited 不含有这个新位置，即新位置没有访问过，还要调用 move 函数来肯定新位置是否能够到达，若这两个条件都知足的话，咱们就对新位置调用递归函数。注意递归函数调用完成后，咱们要回到调用以前的状态，由于这里的 robot 是带了引用号的，是全局通用的，因此要回到以前的状态。回到以前的状态很简单，由于这里的机器人的运做方式是先转到要前进的方向，才能前进。那么咱们后退的方法就是，旋转 180 度，前进一步，再转回到原来的方向。

同理，咱们在按顺序试上->右->下->左的时候，每次机器人要向右转一下，由于 move 函数只能探测前方是否能到达，因此咱们必须让机器人转到正确的方向，才能正确的调用 move 函数。若是用过扫地机器人的童鞋应该会有影响，当前方有障碍物的时候，机器人圆盘会先转个方向，而后再继续前进，这里要实现的机制也是相似的，参见代码以下：

class Solution {
public:
    vector<vector<int>> dirs{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    void cleanRoom(Robot& robot) {
        unordered_set<string> visited;
        helper(robot, 0, 0, 0, visited);
    }
    void helper(Robot& robot, int x, int y, int dir, unordered_set<string>& visited) {
        robot.clean();
        visited.insert(to_string(x) + "-" + to_string(y));
        for (int i = 0; i < 4; ++i) {
            int cur = (i + dir) % 4, newX = x + dirs[cur][0], newY = y + dirs[cur][1];
            if (!visited.count(to_string(newX) + "-" + to_string(newY)) && robot.move()) {
                helper(robot, newX, newY, cur, visited);
                robot.turnRight();
                robot.turnRight();
                robot.move();
                robot.turnLeft();
                robot.turnLeft();
            }
            robot.turnRight();
        }
    }
};