|
1 | 1 | classSolution { |
| 2 | +privatefinalint[][]DIRS = {{1,0}, {0,1}, {-1,0}, {0, -1}, {1,1}, {-1,1}, {1, -1}, {-1, -1}}; |
| 3 | + |
2 | 4 | publicintshortestPathBinaryMatrix(int[][]grid) { |
3 | | -intn =grid.length; |
4 | | -if (n ==0 ||grid[0][0] ==1 ||grid[n -1][n -1] ==1) { |
| 5 | +if (grid[0][0] ==1) { |
5 | 6 | return -1; |
6 | 7 | } |
| 8 | +intnumRows =grid.length; |
| 9 | +intnumCols =grid[0].length; |
| 10 | +boolean[][]visited =newboolean[numRows][numCols]; |
7 | 11 | Queue<int[]>queue =newLinkedList<>(); |
8 | | -intnumberOfSteps =0; |
9 | | -boolean[][]visited =newboolean[n][n]; |
10 | | -queue.add(newint[] {0,0}); |
| 12 | +queue.add(newint[]{0,0}); |
11 | 13 | visited[0][0] =true; |
| 14 | +intnumOfSteps =0; |
12 | 15 | while (!queue.isEmpty()) { |
| 16 | +numOfSteps++; |
13 | 17 | intsize =queue.size(); |
14 | 18 | while (size-- >0) { |
15 | 19 | int[]removed =queue.remove(); |
16 | | -if (removed[0] ==n -1 &&removed[1] ==n -1) { |
17 | | -returnnumberOfSteps +1; |
| 20 | +intx =removed[0]; |
| 21 | +inty =removed[1]; |
| 22 | +if (x ==numRows -1 &&y ==numCols -1) { |
| 23 | +returnnumOfSteps; |
18 | 24 | } |
19 | | -for (int[]dir :EIGHT_DIRS) { |
20 | | -intnewX =removed[0] +dir[0]; |
21 | | -intnewY =removed[1] +dir[1]; |
22 | | -if (newX >=0 |
23 | | - &&newX <n |
24 | | - &&newY >=0 |
25 | | - &&newY <n |
26 | | - && !visited[newX][newY] |
27 | | - &&grid[newX][newY] ==0) { |
28 | | -queue.add(newint[] {newX,newY}); |
| 25 | +for (int[]dir :DIRS) { |
| 26 | +intnewX =x +dir[0]; |
| 27 | +intnewY =y +dir[1]; |
| 28 | +if (newX >=0 &&newY >=0 &&newX <numRows &&newY <numCols && !visited[newX][newY] &&grid[newX][newY] ==0) { |
| 29 | +queue.add(newint[]{newX,newY}); |
29 | 30 | visited[newX][newY] =true; |
30 | 31 | } |
31 | 32 | } |
32 | 33 | } |
33 | | -numberOfSteps++; |
34 | 34 | } |
35 | 35 | return -1; |
36 | 36 | } |
37 | | - |
38 | | -privatestaticfinalint[][]EIGHT_DIRS = { |
39 | | - {0,1},{0,-1},{1,0},{-1,0},{1,-1},{-1,1},{-1,-1},{1,1}}; |
40 | 37 | } |