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 = 2147483647to representINFas 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
Similar:
- 130. Surrounded Regions
- 200. Number of Islands
- 317. Shortest Distance from All Buildings
1 public class Solution { 2 public void wallsAndGates(int[][] rooms) { 3 if (rooms.length == 0 || rooms[0].length==0) 4 return; 5 Queue<int[]> queue = new LinkedList<int[]>(); 6 int m = rooms.length; 7 int n = rooms[0].length; 8 int[] shift = {1, 0, -1, 0, 1}; 9 for (int i=0; i<m; i++) 10 for (int j=0; j<n; j++) { 11 if (rooms[i][j] == 0) { 12 queue.offer(new int[] {i,j}); 13 } 14 } 15 int level = 1; 16 while (!queue.isEmpty()) { 17 int size = queue.size(); 18 while (size > 0) { 19 int[] pt = queue.poll(); 20 // rooms[pt[0]][pt[1]] = level; 21 for (int k = 0; k < 4; k++) { 22 int r = pt[0] + shift[k]; 23 int c = pt[1] + shift[k+1]; 24 if (r>=0 && r<m && c>=0 && c<n && rooms[r][c] == Integer.MAX_VALUE) { 25 rooms[r][c] = level; // set here in case point [1][1] would put [1][0] in the queue Twice 26 queue.offer(new int[] {r,c}); 27 } 28 } 29 size--; 30 } 31 level++; 32 } 33 return; 34 } 35 }