Leetcode489 Robot Room Cleaner

Posted on In

题目描述

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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.

Note:

  • 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.

解析

这是一道很有意思的题目，是我刷leetcode以来见到的最奇怪的题目之一，题目是说有一个机器人，提供move，turnLeft，turnRight，clean四个API，move为每次移动一格，要求清洁所有房间，可以理解为允许在一个二维平面内，上下左右地移动，要求遍历所有房间。

不过很有意思的是，这个题目没有给地图，题目中说了初始位置，但是只在测试的时候用，也就是说并不会当作参数传进来，也就是说这个robot是属于瞎摸索的状态，此外移动只能面朝前移动，所以我们必须时刻记录robot朝向的位置，要求在这种情况下设计算法，遍历每一个能遍历的点，如果不能移动，move函数会返回false。

其实抽象出来这个题目的本质还是一个DFS，我们要随时保存访问过的节点，由于初始位置不清楚，所以干脆直接初始化位置定为（0，0），然后上下左右移动，将所到达的点保存即可。

不过与通常情况下我们DFS回溯到以前的节点不需要再做什么特殊操作，然而由于本题有一个转向的元素，我们必须保证退回到原来的节点的时候机器人转向一致。

注意到turnLeft，turnRight都是每次旋转90度，也就是每四次一个轮回，利用这个性质，我们可以将机器人在返回原来的位置的时候，调整原先的转向。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//visited是一个存String的hash表，将两个坐标转化为String存起来
HashSet<String> visited;
// dx，dy用来保存上下左右四个位置，方便搜索时遍历调用
int[] dx = {0,1,0,-1};
int[] dy = {1,0,-1,0};
public void cleanRoom(Robot robot) {
    
    visited = new HashSet<>();
    doClean(0, 0, 0, robot);
}
//这里的direction可以用作dx，dy里的index，0是向前，1是向右，2是向下，3是向左
private void doClean(int x, int y, int direction, Robot robot){
    //每次默认开始时robot已经在x，y里了，但还没有做清洁
    String coord = Integer.toString(x)  + "," + Integer.toString(y);
    visited.add(coord);        
    robot.clean();
    for(int i = 1; i <= 4; i++){
        robot.turnRight();
        int newDirection = (direction + i) % 4;
        int newx = x + dx[newDirection];
        int newy = y + dy[newDirection];
        String newCoord = Integer.toString(newx) + "," + Integer.toString(newy);
        if(visited.contains(newCoord))
            continue;
        if(robot.move())
            doClean(newx, newy, newDirection, robot);
    }
    // 四次之后方向与刚进来的时候的方向是一致的
    // 连续左转两次，与当前方向相反后可移动到上一个点，从哪里来，回哪里去
    // 不过刚回去的时候朝向是反的，得再转两次，把朝向调正确
    robot.turnLeft();
    robot.turnLeft();
    robot.move();
    robot.turnLeft();
    robot.turnLeft();
}

总结

很有意思的一道DFS题，需要在给定情境下能够活学活用，处理一些正常写DFS不会遇到的边界情况，弄清楚这些后，写起来还是很有意思的，万变不离其宗本质还是一个Backtracing以及DFS。