题目描述

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.

样例

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.

算法：DFS

(暴力枚举) $O(n^2)$

• 思路是DFS不会有太大问题，
• 难点在于恢复现场这一步
• 如何恢复？官方题解给出的go_back + turn_right很精巧！
  • 四个方向探索，满足：之前没被探索、没撞墙则move to next
  • 完事后go_back：右转+右转+前进+右转+右转
  • 四方向for循环最后一步的turn right保证了恢复现场，与后续(stack中前一步)go_back形成配合
  • 核心思路就是回溯过程保证机器人的朝向位置与上次进栈状态完全一致

C++ 代码

const int N=1003;

class Solution {
public:
    vector<vector<int>> ds={{-1,0},{0,1},{1,0},{0,-1}};
    unordered_set<int> S;

    void cleanRoom(Robot& robot) {
        dfs(robot, 0, 0, 0);
    }

    void dfs(Robot& robot, int cd, int r, int c) {
        S.insert(r*N+c);
        robot.clean();

        for(int i=0; i<4; i++){
            int ncd=(cd+i)%4;
            int nr=r+ds[ncd][0], nc=c+ds[ncd][1];
            if(!S.count(nr*N+nc) && robot.move()){
                dfs(robot, ncd, nr, nc);
                go_back(robot);
            }
            robot.turnRight();
        }
    }

    void go_back(Robot& robot){
        robot.turnRight();
        robot.turnRight();
        robot.move();
        robot.turnRight();
        robot.turnRight();
    }
};