Robot Room Cleaner

题目
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.

答案
因为不提供方向和初始位置，所以我们只要自己设定初始位置为(0,0), 初始方向为上就建造出一个房间了。

class Solution {
    Set<String> visited = new HashSet<>();
    Set<String> blocked = new HashSet<>();

    public String makeKey(int x, int y) { return Integer.toString(x) + ":" + Integer.toString(y); }
    
    public void cleanRoom(Robot robot) {
        dfs(robot, 0, 0, 0);
    }
    
    public void dfs(Robot robot, int x, int y, int curr_dir) {
        boolean ret = false;
        String key = "";
        int[][] delta = new int[][]{{-1, 0},{0, -1},{1, 0},{0, 1}};
        int nx, ny;
        // Clean current position
        robot.clean();
        
        // Mark current position as visited
        visited.add(makeKey(x, y));    
        
        // Explore 4 directions
        for(int i = 0; i < 4; i++) {
            // Calculate new direction and new position
            int new_dir = (curr_dir + i) % 4;
            nx = x + delta[new_dir][0];
            ny = y + delta[new_dir][1];
            key = makeKey(nx, ny);
            if(visited.contains(key) || blocked.contains(key)) continue;
            
            for(int j = 0; j < i; j++) robot.turnLeft();

            ret = robot.move();
            if(!ret) {
                blocked.add(key);
                for(int j = 0; j < i; j++) robot.turnRight();
            }
            else {
                dfs(robot, nx, ny, new_dir);

                // Go back to previous position
                robot.turnLeft();
                robot.turnLeft();
                robot.move();

                // Fix direction
                // We are now facing new_dir + 2 left turns
                // Should face curr_dir
                int dir_now = (new_dir + 2) % 4;
                for(int j = 0; j < Math.abs(dir_now - curr_dir); j++) {
                    if(curr_dir > dir_now) robot.turnLeft();
                    else robot.turnRight();
                }
            }
        } 
    }
}