489. Robot Room Cleaner

https://en.wikipedia.org/wiki/Maze-solving_algorithm#Wall_follower

1.本題還是要 4 個方向, why? 因為還是得要知道有沒有走過某個 cell, 這題 visited 用 HashSet<String> 比較方便

move 只能提供是不是碰到 wall 的資訊

方向要訂正確, 東南西北, 因為我們總是 turnright, 順時針

2. 真的能走時, 走完 dfs, 要 backtracking

3.

turnRight() 寫在最後

所以其實是先 move()

如果不能 move(), 或走過了, 才要 turnRight()

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
*/