0489. Robot Room Cleaner

tags: Leetcode Hard DFS

Link: https://leetcode.com/problems/robot-room-cleaner/description/

思路

难点在于机器人是第一视角 所以我们需要手动从机器人的角度实现dfs(旋转 找下一个方向)
如果现在机器人的方向是朝北 我们希望机器人走到东边的一个格子 就需要先turnRight()然后再move()
接着我们需要旋转180度再往前走回到原来的格子 下一个方向是朝南 因此我们需要先再转180度 让机器人朝东 接着循环刚才的动作先turnRight()再move()

Code

class Solution {
    public void cleanRoom(Robot robot) {
        Set<String> set = new HashSet<>();
        set.add("0,0");
        dfs(0, 0, 0, set, robot);
    }
    private void dfs(int x, int y, int curDir, Set<String> set, Robot robot){
        robot.clean();
        int[][] dirs = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
        for(int i=1; i<=4; i++){
            robot.turnRight();
            int nextDir = (i+curDir)%4;
            int nextx = x+dirs[nextDir][0];
            int nexty = y+dirs[nextDir][1];
            if(!set.contains(nextx+","+nexty) && robot.move()){
                set.add(nextx+","+nexty);
                dfs(nextx, nexty, (curDir+i)%4, set, robot);
                robot.turnLeft();
                robot.turnLeft();
                robot.move();
                robot.turnLeft();
                robot.turnLeft();
            }
        }
    }
}