489. Robot Room Cleaner

/**
 * // 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 {
    public void cleanRoom(Robot robot) {
        dfs(robot, 0, 0, 0);
    }

    void dfs(Robot robot, int i, int j, int dir)
    {
        if(map.containsKey(i) && map.get(i).contains(j)) return;
        // System.out.printf("%d %d %d\n", i, j, dir);
        if(!map.containsKey(i)) map.put(i, new HashSet<>());
        map.get(i).add(j);
        robot.clean();
        int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
        // try 4 different directions
        for(int k = 0; k < 4; k++)
        {
            if(robot.move())
            {
                dfs(robot, i + dx[dir], j + dy[dir], dir);
                robot.turnLeft();
                robot.turnLeft();
                robot.move();
                robot.turnLeft();
                robot.turnLeft();
            }

            robot.turnLeft();
            dir = (dir + 1) % 4;
        }
    }

    Map<Integer, Set<Integer>> map = new HashMap<>();
}