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。

例如，如果网格像-

橙色单元格将成为路径。长度是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