489. Robot Room Cleaner

 一刷 07/2022

Version #1 Backtracking

重点是每次要回到原位原方向

而且每次当前方向要传到下一层，因为需要知道进入当前层的时候robot的方向

同时如果不能move的时候也要记得转

Time O(MN)

Space O(MN)

Runtime: 8 ms, faster than 69.21% of Java online submissions for Robot Room Cleaner.

Memory Usage: 44.9 MB, less than 75.18% of Java online submissions for Robot Room Cleaner.

class Solution {

    public void cleanRoom(Robot robot) {

        // try to turn 4 directions and move

        Set<Pair<Integer, Integer>> visited = new HashSet<>();

        clean(robot, 0, 0, visited, 0);

    }

    

    private int[] dx = new int[]{0, 1, 0, -1};

    private int[] dy = new int[]{1, 0, -1, 0};

    

    private void clean(Robot robot, int y, int x, Set<Pair<Integer, Integer>> visited, int dir) {

        if (!visited.add(new Pair(y, x))) {

            return;

        }

        robot.clean();

        // 

        for (int i = 0; i < 4; i++) {

            int nd = (dir + i) % 4;

            if (robot.move()) {

                clean(robot, y + dy[nd], x + dx[nd], visited, nd);

                robot.turnLeft();

                robot.turnLeft();

                robot.move();

                robot.turnLeft();

            } else {

                robot.turnRight();

            }

        }

    }

}