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

  • Z时代
  • 2024-01-10
  • 分类：综合

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

例如，如果网格像-

000
110
110

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

    以上是 C ++中二进制矩阵的最短路径 的全部内容， 来源链接： utcz.com/z/343547.html

    回到顶部