You are given a m x n 2D grid initialized with these three possible values.
-1
- A wall or an obstacle.0
- A gate.INF
- Infinity means an empty room. We use the value231 - 1 = 2147483647
to representINF
as you may assume that the distance to a gate is less than2147483647
.
Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with
INF
.
For example, given the 2D grid:
INF -1 0 INF INF INF INF -1 INF -1 INF -1 0 -1 INF INF
After running your function, the 2D grid should be:
3 -1 0 1 2 2 1 -1 1 -1 2 -1 0 -1 3 4
Basic BFS problem. Add all cells of gates to the queue. Now for each cell polled out, check all its neighbors, update all neighbors that are valid cells and have distance to a gate larger than current one plus one.
public void wallsAndGates(int[][] rooms) { Queuequeue = new LinkedList (); int r = rooms.length, c = rooms[0].length; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (rooms[i][j] == 0) { queue.add(i * c + j); } } } int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; while (!queue.isEmpty()) { int curr = queue.poll(); for (int[] d : dirs) { int x = curr / c + d[0]; int y = curr % c + d[1]; if (x < 0 || x >= r || y < 0 || y >= c || rooms[x][y] <= rooms[x - d[0]][y - d[1]] + 1) { continue; } rooms[x][y] = rooms[x - d[0]][y - d[1]] + 1; queue.add(x * c + y); } } }
No comments:
Post a Comment