C++ 이진 행렬의 최단 경로

N x N 정사각형 그리드가 있다고 가정하고 각 셀은 비어 있거나(0) 차단되어 있습니다(1). 왼쪽 상단에서 오른쪽 하단까지의 명확한 경로는 -

• 인접한 셀 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가 비어 있지 않은 동안

  • curr :=q에서 앞점, q에서 앞점 삭제

  • x :=curr의 x 값, y :=curr의 y 값, c :=curr의 c 값

  • x =n – 1이고 y =n – 1이면 c

    를 반환합니다.

  • c를 1 증가

  • 0에서 7 사이의 i에 대해

    • X :=x + d[i, 0], Y :=y + d[i, 1]

    • 범위 0과 n의 X와 범위 0과 n의 y, 그리고 grid[X, Y]가 0이면

      • 그리드[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