forked from neetcode-gh/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
0286-walls-and-gates.java
39 lines (37 loc) · 1.44 KB
/
0286-walls-and-gates.java
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
37
38
39
//Same as rotting oranges
//Time complexity will be O(N^2) since we are basically traversing every value in the grid.
class Solution {
public void wallsAndGates(int[][] rooms) {
Queue<int[]> q = new LinkedList<>();
int m = rooms.length;
int n = rooms[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (rooms[i][j] == 0) q.add(new int[] { i, j });
}
}
if (q.size() == 0) return;
int[][] dirs = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };
while (!q.isEmpty()) {
int[] cur = q.poll();
int row = cur[0];
int col = cur[1];
for (int[] dir : dirs) {
int x = row + dir[0];
int y = col + dir[1];
if (
x >= m ||
y >= n ||
x < 0 ||
y < 0 ||
rooms[x][y] != Integer.MAX_VALUE
) continue;
q.add(new int[] { x, y });
//since cur is basically the index of door (which is equal to 0)
//So, we can just grab that value (rooms[row][col]) and add 1 to it and change it every time
rooms[x][y] = rooms[row][col] + 1;
//So, one level further from door (value 0) is equal to 1. Now, we do bfs from that position so value will be 2 and so on.
}
}
}
}