在一個 N × N 的方形網格中,每個單元格有兩種狀态:空(0)或者阻塞(1)。
一條從左上角到右下角、長度為 k 的暢通路徑,由滿足下述條件的單元格 C_1, C_2, ..., C_k 組成:
相鄰單元格 C_i 和 C_{i+1} 在八個方向之一上連通(此時,C_i 和 C_{i+1} 不同且共享邊或角)
C_1 位于 (0, 0)(即,值為 grid[0][0])
C_k 位于 (N-1, N-1)(即,值為 grid[N-1][N-1])
如果 C_i 位于 (r, c),則 grid[r][c] 為空(即,grid[r][c] == 0)
傳回這條從左上角到右下角的最短暢通路徑的長度。如果不存在這樣的路徑,傳回 -1 。
代碼
class Solution {
public int shortestPathBinaryMatrix(int[][] grid) {
if(grid[0][0]==1) return -1;
int[][] dir=new int[][]{{-1,0},{1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
Queue<int[]> queue=new LinkedList<>();
int n=grid.length;
int level=1;
queue.add(new int[]{0,0});
boolean[][] check=new boolean[n][n];
check[0][0]=true;
while (!queue.isEmpty())
{
int size=queue.size();
for(int i=0;i<size;i++)
{
int[] temp=queue.poll();
int x=temp[0],y=temp[1];
if(x==n-1&&y==n-1) return level;
for(int[] d:dir)
{
int nextX=x+d[0],nextY=y+d[1];
if(bound(nextX,nextY,n,n)&&grid[nextX][nextY]!=1&&!check[nextX][nextY])
{
queue.add(new int[]{nextX,nextY});check[nextX][nextY]=true;
}
}
}
level++;
}
return -1;
}
public boolean bound(int x,int y,int n,int m){
return x>=0&&x<n&&y>=0&&y<m;
}
}