C ++中二进制矩阵的最短路径
假设我们有一个NxN的正方形网格，其中每个单元格为空或块状(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。
例如，如果网格像-
橙色单元格将成为路径。长度是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