> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/dfs/tips/489.-robot-room-cleaner.md).

# 489. Robot Room Cleaner

<https://en.wikipedia.org/wiki/Maze-solving_algorithm#Wall_follower>

![](/files/jqCNyKI1OQRZLLJuYMNy)

![](/files/Afh0p61f7pQeptA4q2QP)

1.本題還是要 4 個方向, why? 因為還是得要知道有沒有走過某個 cell, 這題 visited 用 HashSet\<String> 比較方便

move 只能提供是不是碰到 wall 的資訊

方向要訂正確,  東南西北, 因為我們總是 turnright, 順時針

2\. 真的能走時, 走完 dfs, 要 backtracking&#x20;

3\.

turnRight() 寫在最後

所以其實是先 move()

如果不能 move(), 或走過了, 才要  turnRight()

```
T: O(n), n is the cell numbers which robot moved
S: O(n), Set<String> visited: record cell numbers which robot visited
```

```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 {
    private static final int[][] DIRS = {{1,0}, {0,-1}, {-1,0}, {0, 1}}; // east, south, west, north
    public void cleanRoom(Robot robot) {
        dfs(0, 0, 0, robot, new HashSet<>());
    }
    private void dfs(int x, int y, int dir, Robot robot, Set<String> visited) {
        robot.clean();
        visited.add(x + "#" + y);
        
        for (int i = 0; i < 4; i++) {
            int nextDir = (dir + i)%4; // don't override dir! 
            
            int nextX = x + DIRS[nextDir][0];
            int nextY = y + DIRS[nextDir][1];
            
            if (!visited.contains(nextX + "#" + nextY) && robot.move()) {
                dfs(nextX, nextY, nextDir, robot, visited);
                // like backtracking, 機器人回到原本位置和原本方向
                robot.turnRight();
                robot.turnRight();
                robot.move();
                robot.turnRight();
                robot.turnRight();
            }
            // cant move, so turn right
            robot.turnRight(); 
        }

    }
}

/*
where 0 represents a wall and 1 represents an empty slot.

can move forward, turn left, or turn right. Each turn is 90 degrees.

When the robot tries to move into a wall cell, its bumper sensor detects the obstacle, 
and it stays on the current cell.

boolean move(); => ob => false

T: O(n), n is the cell numbers which robot moved
S: O(n), Set<String> visited: record cell numbers which robot visited
*/
```