本文共 1278 字，大约阅读时间需要 4 分钟。

1. 题目

在一个 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 。提示：1 <= grid.length == grid[0].length <= 100grid[i][j] 为 0 或 1

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/shortest-path-in-binary-matrix

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

• 8个方向可走，题目意思是路径上点的个数，step初始为1

class Solution {
   public:    int shortestPathBinaryMatrix(vector
   
    
     >& grid) {
       	int m = grid.size(), n = grid[0].size(), i, j, x, y, k, step = 1, size;    	if(grid[0][0]==1 || grid[m-1][n-1]==1)    		return -1;    	vector
     
      
       > dir = {
   {
   1,0},{
   0,1},{
   0,-1},{
   -1,0},{
   1,1},{
   -1,-1},{
   1,-1},{
   -1,1}};    	queue
       
        
         > q; q.push({ 0,0});//坐标x,y grid[0][0] = 1;//访问过 while(!q.empty()) { size = q.size(); while(size--) { i = q.front()[0]; j = q.front()[1]; if(i==m-1 && j==n-1) return step; q.pop(); for(k = 0; k < 8; ++k) { x = i + dir[k][0]; y = j + dir[k][1]; if(x>=0 && x
         
          =0 && y
         
        
       
      
     
    
   

208 ms 27.1 MB

转载地址：https://michael.blog.csdn.net/article/details/106029651 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！