# 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>& room) { const int m = room.size(); const int n = room.size(); const vector 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> seen(m, vector(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.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) 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))