1091, Shortest path in binary matrix

1091, Shortest path in binary matrix

====

BFS,

Shortest path,

Path existed

====

1. 題目給予vec<vec<int>>matrix

從左上 欲走到右下

路徑上只能是0 可以走八個方向

2. 一個queue< pair<int,int>>做BFS

一個vec<vec<bool>> visited記錄走過

3. 起點是左上

找它的鄰近加入queue

紀錄每次queue.size

而後每次找鄰近 且 matrix[][]==0 加入queue

4. 每次round++

當有座標碰到右下

return round(左上）

====

class Solution {

public:

int shortestPathBinaryMatrix(.vec<vec<int>>& grid ){

  int m= grid.size(), n= grid[0].size()

  if( grid[0][0]!=0 || grid[m-1][n-1]!=0 ) return -1

  queue< pair<int,int>> pq

  pq.push({1,0}), pq.push({0,1}), pq.push({1,1})

  vec<vec<bool>> visited=(m, vec<bool>(n, false))

  int res=1 //第一輪

  while(!pq.empty()){

    int qSize= pq.size()

    for(int t-qSize){

      auto qFront= pq.front()

      pq.pop()

      int x= qFront.first

      int y= qFront.second

      

      if(x==m-1 && y==n-1) return res+1 //第n輪加上右下+1

      if(x>=0 && y>=0 && x<m && y<n && !visited[x][y] && grid[x][y]==0){

        visited[x][y]=true

        pq.push({x-1,y-1}), pq.push({x-1,y}), pq.push({x-1,y+1})

        pq.push({x,y-1}), pq.push({x,y+1})

        pq.push({x+1,y-1}), pq.push({x+1,y}), pq.push({x+1,y+1})

      }//if

    }//for qSize

    res++

  }//while q.empty

  return -1

}

};