软件测试工程师培训机构哪家好_网站空间申请_西安做网页的公司_广告网站策划方案

力扣1091. 二进制矩阵中的最短路径

题目

题目解析及思路

题目要求找到一条左上到右下的最短路径

八方向bfs板子

代码

class Solution {int dx[8] = {0,1,0,-1,1,1,-1,-1},dy[8] = {1,0,-1,0,-1,1,-1,1};
public:int shortestPathBinaryMatrix(vector<vector<int>>& grid) {int n = grid.size();if(grid[0][0] == 1) return -1;queue<pair<int,int>> q;vector<vector<int>> dis(n,vector<int>(n,INT_MAX));auto bfs = [&]()->void{while(!q.empty()){auto [x,y] = q.front();q.pop();for(int i=0;i<8;i++){int sx = x + dx[i];int sy = y + dy[i];if(sx < 0 || sx >= n || sy < 0 || sy >= n || grid[sx][sy] == 1){continue;}if(dis[sx][sy] > dis[x][y] + 1){dis[sx][sy] = dis[x][y] + 1;q.emplace(sx,sy);}}}};q.emplace(0,0);dis[0][0] = 1;bfs();return dis[n-1][n-1] > INT_MAX / 2 ? -1 : dis[n-1][n-1];}
};