假设我们有一个N x N的正方形网格，其中每个单元格为空或块状(1)。当且仅当它由单元格C_1，C_2，...，C_k组成时，从左上角到右下角的畅通路径的长度为k，使得-
-
相邻像元C_i和C_ {i + 1}是8方向连接的（因此它们是不同的并且共享边或角）
-
C_1位于位置(0,0)
-
C_k位于位置(N-1,N-1)
-
如果C_i位于(r,c)，则grid [r，c]为空或包含0
我们必须找到从左上角到右下角的最短清晰路径的长度。如果没有这样的路径，则返回-1。
例如，如果网格像-
| 0 | 0 | 0 |
| 1 | 1 | 0 |
| 1 | 1 | 0 |
橙色单元格将成为路径。长度是4
为了解决这个问题，我们将遵循以下步骤-
-
定义一个方向数组，它将容纳8对以移动8个不同的方向。所以这个数组就像[[1,1]，[1，-1]，[-1,1]，[1,0]，[0,1]，[-1，-1]，[0，- 1]，[-1,0]]
-
主要部分将以网格作为输入，其行为如下所示-
-
定义点队列，q，n：=行数
-
如果grid [0，0]为0，则建立一个新点p(0,0,1)，将p插入q，然后使grid [0，0]：= 1
-
当q不为空时
-
X：= x + d [i，0]，Y：= y + d [i，1]
-
如果X的范围为0，n的范围为y，y的范围为0和n，则y的范围为grid [X，Y]，则
-
grid [X，Y]：= 1
-
将新点p(X,Y,c)插入q
-
curr：= q的前沿，q的前沿
-
x：= x当前值，y：= y当前值，c：= c当前值
-
如果x = n – 1且y = n – 1，则返回c
-
将c增加1
-
对于我在0到7范围内
-
返回-1
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
int d[8][2] = {{1, 1}, {1, -1}, {-1, 1}, {1, 0}, {0, 1}, {-1, -1},
{0, -1}, {-1, 0}};
struct point{
int x, y, c;
point(int a, int b, int z){
x = a;
y = b;
c = z;
}
};
class Solution {
public:
int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
queue <point> q;
int n = grid.size();
if(!grid[0][0]){
q.push(point(0, 0, 1));
grid[0][0] = 1;
}
while(!q.empty()){
point curr = q.front();
q.pop();
int x = curr.x;
int y = curr.y;
int c = curr.c;
if(x == n-1 && y == n-1)return c;
c++;
for(int i = 0; i < 8; i++){
int X = x + d[i][0];
int Y = y + d[i][1];
if(X >= 0 && X < n && Y >= 0 && Y < n &&
!grid[X][Y]){
grid[X][Y] = 1;
q.push(point(X, Y, c));
}
}
}
return -1;
}
};
main(){
vector<vector<int>> v = {{0,0,0},{1,1,0},{1,1,0}};
Solution ob;
cout << (ob.shortestPathBinaryMatrix(v));
}
输入值
[[0,0,0],[1,1,0],[1,1,0]]
输出结果
4
