# 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
*/
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/dfs/tips/489.-robot-room-cleaner.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.