|
1 | 1 | classSolution { |
2 | | -publicintmaxDistance(int[][]grid) { |
3 | | -if (grid.length ==0 ||grid[0].length ==0) { |
4 | | -return -1; |
| 2 | +privatefinalint[][]DIRS = {{1,0}, {-1,0}, {0, -1}, {0,1}}; |
| 3 | + |
| 4 | +publicintmaxDistance(int[][]grid) { |
| 5 | +Queue<int[]>queue =newLinkedList<>(); |
| 6 | +intnumRows =grid.length; |
| 7 | +intnumCols =grid[0].length; |
| 8 | +for (inti =0;i <numRows;i++) { |
| 9 | +for (intj =0;j <numCols;j++) { |
| 10 | +if (grid[i][j] ==1) { |
| 11 | +queue.add(newint[]{i,j}); |
5 | 12 | } |
6 | | -int[][]dirs = {{1,0}, {0,1}, {-1,0}, {0, -1}}; |
7 | | -boolean[][]visited =newboolean[grid.length][grid[0].length]; |
8 | | -Queue<int[]>queue =newLinkedList<>(); |
9 | | -for (inti =0;i <grid.length;i++) { |
10 | | -for (intj =0;j <grid[0].length;j++) { |
11 | | -if (grid[i][j] ==1) { |
12 | | -queue.add(newint[]{i,j}); |
13 | | -visited[i][j] =true; |
14 | | - } |
15 | | - } |
16 | | - } |
17 | | -intmaxDist = -1; |
18 | | -while (!queue.isEmpty()) { |
19 | | -intsize =queue.size(); |
20 | | -while (size-- >0) { |
21 | | -int[]curr =queue.remove(); |
22 | | -for (int[]dir :dirs) { |
23 | | -intx =curr[0] +dir[0]; |
24 | | -inty =curr[1] +dir[1]; |
25 | | -if (x >=0 &&x <grid.length &&y >=0 &&y <grid[0].length && !visited[x][y] &&grid[x][y] ==0) { |
26 | | -visited[x][y] =true; |
27 | | -queue.add(newint[]{x,y}); |
28 | | - } |
29 | | - } |
30 | | - } |
31 | | -maxDist++; |
| 13 | + } |
| 14 | + } |
| 15 | +if (queue.isEmpty() ||queue.size() ==numRows *numCols) { |
| 16 | +return -1; |
| 17 | + } |
| 18 | +intdistance =0; |
| 19 | +while (!queue.isEmpty()) { |
| 20 | +intsize =queue.size(); |
| 21 | +while (size-- >0) { |
| 22 | +int[]removed =queue.remove(); |
| 23 | +for (int[]dir :DIRS) { |
| 24 | +intx =removed[0] +dir[0]; |
| 25 | +inty =removed[1] +dir[1]; |
| 26 | +if (x <0 ||y <0 ||x >=numRows ||y >=numCols ||grid[x][y] ==1) { |
| 27 | +continue; |
| 28 | + } |
| 29 | +grid[x][y] =1; |
| 30 | +queue.add(newint[]{x,y}); |
32 | 31 | } |
33 | | - |
34 | | -returnmaxDist ==0 ? -1 :maxDist; |
| 32 | + } |
| 33 | +distance++; |
35 | 34 | } |
| 35 | +returndistance -1; |
| 36 | + } |
36 | 37 | } |