05 August 2008
define a direction array and let the robot traverse on the 2D matrix as long as it can until it came back to the visited box at the same direction after trying at most 5 times (in case it got stuck at the starting point, the 5th time will let it go back to it with the original heading direction).
In order to tell when it is to finish by coming back to the visited state, a hashmap is ued to map coordinates with direction, i.e. {x * n + y, dir} as key - val pair.
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
36
class Solution {
// time = O(m * n), space = O(m * n)
private int[][] dir = new int[][]{ {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
public int numberOfCleanRooms(int[][] room) {
int m = room.length, n = room[0].length;
HashMap<Integer, Integer> map = new HashMap<>();
int x = 0, y = 0, d = 0, count = 1;
map.put(0, 0);
while (true) {
for (int k = d; k < d + 5; k++) {
int i = x + dir[k % 4][0];
int j = y + dir[k % 4][1];
int idx = i * n + j;
if (map.containsKey(idx) && map.get(idx) == k % 4) {
return count;
}
if (i < 0 || i >= m || j < 0 || j >= n || room[i][j] == 1) {
continue;
}
x = i;
y = j;
d = k % 4;
if (!map.containsKey(x * n + j)) {
count++;
}
map.put(x * n + y, d);
break;
}
if (x == 0 && y == 0 && d == 0) {
return count;
}
}
}
}