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();
}
DFS
- 递归出口：如果扫过了就走。
- 本状态处理：扫地，给memo加记录。
- 递归，四方向：转身试挪动，递归，回溯到原位置原方向。
细节
- 本题挪动时控制两个对象：一个是用机器人的API让它真的往四个方向试着挪动；一个是用传统的dxdy计算挪动坐标用于去重。
- 坐标用set去重有小trick，可以以规范化的string形式放入set。
- 本题就是回溯的时候因为API不方便，和一般的dfs写得不太一样而已，别的没什么大变化。
Reference: jasminemzy - leetcode489 - Robot Room Cleaner - hard
