C++のバイナリマトリックスの最短経路

---

N x Nの正方形のグリッドがあり、各セルが空（0）またはブロック（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が空ではない間

  • curr：=qからフロントポイント、qからフロントポイントを削除

  • x：=x currの値、y：=y currの値、c：=ccurrの値

  • x =n –1およびy=n – 1の場合、c

    を返します。

  • cを1増やします

  • 0から7の範囲のiの場合

    • X：=x + d [i、0]、Y：=y + d [i、1]

    • Xが範囲0およびnにあり、yが範囲0およびnにあり、grid [X、Y]が0の場合、

      • grid [X、Y]：=1

      • 新しい点p（X、Y、c）をqに挿入します

• -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