Massive Algorithms: LeetCode 489

LeetCode 489 - Robot Room Cleaner

https://www.cnblogs.com/grandyang/p/9988250.html

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. Each turn it made is 90 degrees.

When it tries to move into a blocked cell, its bumper sensor detects the obstacle and it stays on the current cell.

Design an algorithm to clean the entire room using only the 4 given APIs shown below.

interface Robot {
  // returns true if next cell is open and robot moves into the cell.
  // returns false if next cell is obstacle and robot stays on the current cell.
  boolean move();

  // Robot will stay on the same cell after calling turnLeft/turnRight.
  // Each turn will be 90 degrees.
  void turnLeft();
  void turnRight();

  // Clean the current cell.
  void clean();
}

Example:

Input:
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

Explanation:
All grids in the room are marked by either 0 or 1.
0 means the cell is blocked, while 1 means the cell is accessible.
The robot initially starts at the position of row=1, col=3.
From the top left corner, its position is one row below and three columns right.

Notes:

The input is only given to initialize the room and the robot's position internally. You must solve this problem "blindfolded". In other words, you must control the robot using only the mentioned 4 APIs, without knowing the room layout and the initial robot's position.
The robot's initial position will always be in an accessible cell.
The initial direction of the robot will be facing up.
All accessible cells are connected, which means the all cells marked as 1 will be accessible by the robot.
Assume all four edges of the grid are all surrounded by wall.

https://www.cnblogs.com/yaoyudadudu/p/9321330.html

可以首先想到DFS。

但是这里并没有给出我们矩阵，所以无法判断该位置是否访问过，会出现死循环。

参考了ianhao2的解法。

他用了一个嵌套的hashmap来记录访问的点的相对位置：永远把起点作为（0，0）点来对待。

用set来存储pair也是可以的

这里需要注意的是，用dir来记录方向，因为方向会继承自上一个方向，如果x += dx[i]就会出现方向和坐标不对等的情况。

https://www.cnblogs.com/lightwindy/p/9739158.html

给一个扫地机器人和一个用网格表示的屋子，每个格子是0或者1， 0表示是障碍物，1表示可以通过。机器人有move() ，turnLeft()，turnRight()，clean() 4个API，设计一个算法把整个屋子扫一遍。

注意：房间的布局和机器人的初始位置都是不知道的。机器人的初始位置一定在可以通过的格子里。机器人的初始方向是向上。所以可以通过的格子是联通的。假设网格的四周都是墙。

解法：DFS + Backtracking

Different from regular dfs to visit all, the robot move() function need to be called, backtrack needs to move() manually and backtracking path shold not be blocked by visited positions
- IMPORTANT: Mark on the way in using set, but `backtrack directly without re-check against set`
- Backtrack: turn 2 times to revert, move 1 step, and turn 2 times to revert back.

    int[] dx = {-1, 0, 1, 0};

    int[] dy = {0, 1, 0, -1};

    public void cleanRoom(Robot robot) {

        // use 'x@y' mark visited nodes, where x,y are integers tracking the coordinates

        dfs(robot, new HashSet<>(), 0, 0, 0); // 0: up, 90: right, 180: down, 270: left

    }

    public void dfs(Robot robot, Set<String> visited, int x, int y, int curDir) {

        String key = x + "@" + y;

        if (visited.contains(key)) return;

        visited.add(key);

        robot.clean();

        for (int i = 0; i < 4; i++) { // 4 directions

            if(robot.move()) { // can go directly. Find the (x, y) for the next cell based on current direction

                dfs(robot, visited, x + dx[curDir], y + dy[curDir], curDir);

                backtrack(robot);

            }

            // turn to next direction

            robot.turnRight();

            curDir += 1;

            curDir %= 4;

        }

    }

简单翻译一下，给一个二维矩阵，里面只有0和1两种数字，0表示这个Node是阻塞的，1表示该Node是畅通的。题目给出了Robot的interface，里面是4个Robot的Operation。现在问题是设计cleanRoom(Robot robot) 这个方法，使这个Robot能够clean这个房间中所有畅通的点。

思路：
这是一道典型的DFS题目，我们可以让robot一直向前扫，直到obstructed。此时我们让robot换一个方向(turnLeft or turnRight)，然后继续move。直到robot到达一个点，这个点前后左右不是blocked就是visited的时候，backtracking方法返回。我们就用注释track back后面的5行代码找到robot在这个点之前的状态，继续尝试换一个方向move。当所有的backtracking返回，以及for loop执行完毕后，即可clean all the available point。

public void cleanRoom(Robot robot) {

Set<String> visited = new HashSet<>();

backtracking(robot, visited, 0, 0, 0);

}

int[][] dir = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

private void backtracking(Robot robot, Set<String> visited, int x, int y, int arrow) {

String path = x + "-" + y;

if (visited.contains(path))

return;

visited.add(path);

robot.clean();

for (int i = 0; i < 4; i++) {

if (robot.move()) {

// go all the way till cannot move, then back one step

int nx = x + dir[arrow][0];

int ny = y + dir[arrow][1];

backtracking(robot, visited, nx, ny, arrow);

// trace back

robot.turnLeft();

robot.move();

robot.turnLeft();

}

robot.turnLeft();// or turnRight();

arrow = (arrow + 1) % 4;

}

这道题就是经典的扫地机器人的题目了，之前经常在地里看到这道题，终于被LeetCode收录了进来了，也总算是找到了一个好的归宿了。回归题目，给了我们一个扫地机器人，给了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函数。如果用过扫地机器人的童鞋应该会有影响，当前方有障碍物的时候，机器人圆盘会先转个方向，然后再继续前进，这里要实现的机制也是类似的，参见代码如下：

    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();
        }
    }

http://hehejun.blogspot.com/2018/08/leetcoderobot-room-cleaner.html
这道题还是图的问题，遍历不知道任何信息的图，肯定是用DFS的，所以我们要让robot模仿DFS算法来运作。这里要注意的一个问题是，我们能回到的只是之前节点的位置，而不是像递归的时候栈上存的是当前的整个状态，包括所有变量的值。所以我们要处理好每一次从一个节点出去回来的方向，同时我们也需要记录所有visited过的节点，尽管我们不知道图的任何信息，包括初始位置和方向，我们以当前位置为(0, 0)即可，并且选一个方向为起始方向，然后之后到达的每一个节点，我们方向更新坐标即可。
我们可以自行规定，每当我们进入一个新的节点：

先turnLeft()遍历当前方向的节点
之后每次turnRight()，重复四次，保证我们遍历所有方向的子节点（这里要四次是因为起始节点需要遍历四个方向，非其实节点只需要遍历非入射方向）
最后turnLeft()，面向入射节点

注意第二步当中，有两种情况，如果当前方向子节点是wall，我们直接turnRight()，否则我们只从子节点回来，是和当初入射的方向相反，所以这个时候我们需要turnLeft()来保证我们下一次访问的是原入射方向右边的子节点。

时间复杂度O(V + E)，做法的话递推课循环都可以

https://www.1point3acres.com/bbs/thread-403845-1-1.html

其中关于 `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)

# 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。

LeetCode 489 - Robot Room Cleaner

Labels

Popular Posts