C ++中二进制矩阵的最短路径

假设我们有一个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