489. Robot Room Cleaner

gistfile1.java

/**
 * // 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 {
    
    // when directionA + directionB == 0, A and B are opposite direction
    // Up -> Left -> Down -> Right (Clockwise order)
    private final static int[] DIR = new int[] {1, 2, -1, -2};
    
    private class MyRobot {
        public Robot robot;
        public int x = 0, y = 0;
        public int dirIdx = 0;
        public MyRobot(Robot robot) {
            this.robot = robot;
        }
        public boolean move() {
            boolean res = robot.move();
            if (res) {
                switch (DIR[dirIdx]) {
                    case 1: // UP
                        y--; // notice: go up means decease y
                        break;
                    case -1: // DOWN
                        y++;
                        break;
                    case 2: // LEFT
                        x--;
                        break;
                    case -2: // RIGHT
                        x++;
                        break;
                    default:
                        break;
                }
            }
            return res;
        }
        
        public void turnLeft() {
            robot.turnLeft();
            // Now you see why it has to be clockwise order ;)
            dirIdx = (dirIdx + 1) % 4;
        }
        
        public void turnRight() {
            robot.turnRight();
            dirIdx = dirIdx > 0 ? (dirIdx - 1) % 4 : 3;
        }
        
        public void clean() {
            robot.clean();
        }
    }
    
    public void cleanRoom(Robot robot) {
        Map<Integer, Set<Integer>> cleaned = new HashMap<>();
        // The starting location does not have a parent location
        // So we won't "go back"
        MyRobot myRobot = new MyRobot(robot);
        myRobot.clean();
        add(cleaned, myRobot.x, myRobot.y);
        for (int i = 0; i < 4; i++) {
            if (myRobot.move()) {
                dfs(myRobot, cleaned);
            }
            myRobot.turnRight();
        }
    }
    
    private void dfs(MyRobot myRobot, Map<Integer, Set<Integer>> cleaned) {
        int currentDir = DIR[myRobot.dirIdx];
        if (!contains(cleaned, myRobot.x, myRobot.y)) {
            myRobot.clean();
            add(cleaned, myRobot.x, myRobot.y);
            for (int i = 0; i < 4; i++) {
                if (myRobot.move()) {
                    dfs(myRobot, cleaned);
                }
                myRobot.turnRight();
            }
        }
        // !!! always go back to previsou location with previous direction
        // No matter this location is cleaned or cleaning!!
        while (DIR[myRobot.dirIdx] + currentDir != 0) {
            // Now you see it will be easy to check opposite direction
            myRobot.turnRight();
        }
        myRobot.move();
        myRobot.turnRight();
        myRobot.turnRight();
    }
    
    // Add (x, y) into hashmap
    private void add(Map<Integer, Set<Integer>> map, int x, int y) {
        if (!map.containsKey(x))
            map.put(x, new HashSet<Integer>());
        map.get(x).add(y);
    }
    
    // Check hashmap contains (x, y)
    private boolean contains(Map<Integer, Set<Integer>> map, int x, int y) {
        return map.containsKey(x) && map.get(x).contains(y);
    }

}