Skip to content

2061. Number of Spaces Cleaning Robot Cleaned

  • Time: $O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
 public:
  int numberOfCleanRooms(vector<vector<int>>& room) {
    const int m = room.size();
    const int n = room[0].size();
    const vector<int> dirs{0, 1, 0, -1, 0};
    int ans = 1;
    int i = 0;
    int j = 0;
    int state = 0;  // 0 := right, 1 := down, 2 := left, 3 := up
    vector<vector<int>> seen(m, vector<int>(n));  // seen[i][j] := bitmask
    seen[i][j] |= 1 << state;
    room[i][j] = 2;  // 2 := cleaned

    while (true) {
      const int x = i + dirs[state];
      const int y = j + dirs[state + 1];
      if (x < 0 || x == m || y < 0 || y == n || room[x][y] == 1) {
        // Turns 90 degrees clockwise
        state = (state + 1) % 4;
      } else {
        // Walk to (x, y)
        if (room[x][y] == 0) {
          ++ans;
          room[x][y] = 2;
        }
        i = x;
        j = y;
      }
      if ((seen[i][j] >> state) & 1)
        return ans;
      seen[i][j] |= (1 << state);
    }
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
  public int numberOfCleanRooms(int[][] room) {
    final int m = room.length;
    final int n = room[0].length;
    final int[] dirs = {0, 1, 0, -1, 0};
    int ans = 1;
    int i = 0;
    int j = 0;
    int state = 0;                // 0 := right, 1 := down, 2 := left, 3 := up
    int[][] seen = new int[m][n]; // seen[i][j] := bitmask
    seen[i][j] |= 1 << state;
    room[i][j] = 2; // 2 := cleaned

    while (true) {
      final int x = i + dirs[state];
      final int y = j + dirs[state + 1];
      if (x < 0 || x == m || y < 0 || y == n || room[x][y] == 1) {
        // Turns 90 degrees clockwise
        state = (state + 1) % 4;
      } else {
        // Walk to (x, y)
        if (room[x][y] == 0) {
          ++ans;
          room[x][y] = 2;
        }
        i = x;
        j = y;
      }
      if (((seen[i][j] >> state) & 1) == 1)
        return ans;
      seen[i][j] |= (1 << state);
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
  def numberOfCleanRooms(self, room: List[List[int]]) -> int:
    m = len(room)
    n = len(room[0])
    dirs = [0, 1, 0, -1, 0]
    ans = 1
    i = 0
    j = 0
    state = 0  # 0 := right, 1 := down, 2 := left, 3 := up
    seen = {(i, j, state)}
    room[i][j] = 2  # 2 := cleaned

    while True:
      x = i + dirs[state]
      y = j + dirs[state + 1]
      if x < 0 or x == m or y < 0 or y == n or room[x][y] == 1:
        # Turns 90 degrees clockwise
        state = (state + 1) % 4
      else:
        # Walk to (x, y)
        if room[x][y] == 0:
          ans += 1
          room[x][y] = 2
        i = x
        j = y
      if (x, y, state) in seen:
        return ans
      seen.add((x, y, state))