T: O(n), n is the cell numbers which robot moved
S: O(n), Set<String> visited: record cell numbers which robot visited
/**
* // This is the robot's control interface.
* // You should not implement it, or speculate about its implementation
* interface Robot {
* // Returns true if the cell in front is open and robot moves into the cell.
* // Returns false if the cell in front is blocked and robot stays in the current cell.
* public boolean move();
*
* // Robot will stay in the same cell after calling turnLeft/turnRight.
* // Each turn will be 90 degrees.
* public void turnLeft();
* public void turnRight();
*
* // Clean the current cell.
* public void clean();
* }
*/
class Solution {
private static final int[][] DIRS = {{1,0}, {0,-1}, {-1,0}, {0, 1}}; // east, south, west, north
public void cleanRoom(Robot robot) {
dfs(0, 0, 0, robot, new HashSet<>());
}
private void dfs(int x, int y, int dir, Robot robot, Set<String> visited) {
robot.clean();
visited.add(x + "#" + y);
for (int i = 0; i < 4; i++) {
int nextDir = (dir + i)%4; // don't override dir!
int nextX = x + DIRS[nextDir][0];
int nextY = y + DIRS[nextDir][1];
if (!visited.contains(nextX + "#" + nextY) && robot.move()) {
dfs(nextX, nextY, nextDir, robot, visited);
// like backtracking, 機器人回到原本位置和原本方向
robot.turnRight();
robot.turnRight();
robot.move();
robot.turnRight();
robot.turnRight();
}
// cant move, so turn right
robot.turnRight();
}
}
}
/*
where 0 represents a wall and 1 represents an empty slot.
can move forward, turn left, or turn right. Each turn is 90 degrees.
When the robot tries to move into a wall cell, its bumper sensor detects the obstacle,
and it stays on the current cell.
boolean move(); => ob => false
T: O(n), n is the cell numbers which robot moved
S: O(n), Set<String> visited: record cell numbers which robot visited
*/
