C++에서 장애물 제거가 있는 그리드의 최단 경로

m x n 그리드가 있다고 가정하고 여기서 각 셀은 0 또는 1입니다. 0 셀은 비어 있고 1은 차단됩니다. 한 단계에서 빈 셀에서 위, 아래, 왼쪽 또는 오른쪽으로 이동할 수 있습니다. 최대 k 개의 장애물을 제거할 수 있다고 가정할 때 왼쪽 위 모서리 셀(0, 0)에서 오른쪽 아래 모서리 셀(m-1, n-1)까지 걸어가는 최소 단계 수를 찾아야 합니다. 그런 방법이 없으면 -1을 반환합니다.

따라서 입력이 다음과 같으면

0	0	0
1	1	0
0	0	0
0	1	1
0	0	0

k가 1이고 장애물을 제거하지 않은 최단 경로가 10이므로 출력은 6이 됩니다. 위치 (3,2)에서 장애물이 하나 제거된 최단 경로는 6이 됩니다. 이러한 경로는 (0,0)이 됩니다. (0,1) ~ (0,2) ~ (1,2) ~ (2,2) ~ (3,2) ~ (4,2).

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

ok() 함수를 정의하면 x와 y가 범위 r과 c에 있는지 여부를 확인합니다.
50 x 50 x 2000 크기의 배열 dp를 정의합니다.
x, y, k 및 길이가 있는 하나의 데이터 구조를 정의합니다.
주요 방법에서 다음을 수행하십시오 -
dp를 inf로 채우기
r :=행 개수, c :=열 개수
하나의 대기열 정의 q
(x =0, y =0, k, 길이 =0)을 사용하여 루트라는 데이터 개체를 만듭니다.
루트를 q에 삽입
동안(q가 비어 있지 않음) -
를 수행합니다.
- node :=q의 첫 번째 요소
- q에서 요소 삭제
- x :=node.x, y :=node.y, k :=node.k, 길이 :=node.length
- x가 r - 1과 같고 y가 c - 1과 같으면 -
  - 반환 길이
- (길이 1 증가)
- initialize i :=0의 경우, i <4일 때 업데이트(i를 1만큼 증가), 수행 -
  - nx :=x + dir[i, 0]
  - ny :=y + dir[i, 1]
  - nx가 r - 1과 같고 ny가 c - 1과 같으면 -
    - 반환 길이
  - ok(nx, ny, r, c)가 참이면 -
    - grid[nx, ny]가 0과 같으면 -
      - 길이
        
        (x =nx, y =ny, k, 길이)인 새 데이터 개체를 q
        에 삽입
        
        dp[nx, ny, k] :=길이
    - 그렇지 않으면
      - k> 0이고 길이
        
        (x =nx, y =ny, k =k - 1,length)인 새 데이터 개체를 q
        에 삽입합니다.
        
        dp[nx, ny, k] :=길이
반환 -1

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
int dir [4][2]={{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int dp[50][50][2000];
struct Data{
   int x, y, k, length;
   Data(int a, int b, int c, int d){
      x = a;
      y = b;
      k = c;
      length = d;
   }
};
class Solution {
   public:
   void pre(){
      for (int i = 0; i < 50; i++) {
         for (int j = 0; j < 50; j++) {
            for (int k = 0; k < 2000; k++) {
               dp[i][j][k] = INT_MAX;
            }
         }
      }
   }
   bool ok(int x, int y, int r, int c){
      return (x < r && y < c && x >= 0 && y >= 0);
   }
   int shortestPath(vector<vector<int> >& grid, int k){
      pre();
      int r = grid.size();
      int c = grid[0].size();
      queue<Data> q;
      Data root(0, 0, k, 0);
      q.push(root);
      while (!q.empty()) {
         Data node = q.front();
         q.pop();
         int x = node.x;
         int y = node.y;
         int k = node.k;
         int length = node.length;
         if (x == r - 1 && y == c - 1)
         return length;
         length++;
         for (int i = 0; i < 4; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            if (nx == r - 1 && ny == c - 1)
            return length;
            if (ok(nx, ny, r, c)) {
               if (grid[nx][ny] == 0) {
                  if (length < dp[nx][ny][k]) {
                     q.push(Data(nx, ny, k, length));
                     dp[nx][ny][k] = length;
                  }
               }
               else {
                  if (k > 0 && length < dp[nx][ny][k]) {
                     q.push(Data(nx, ny, k - 1, length));
                     dp[nx][ny][k] = length;
                  }
               }
            }
         }
      }
      return -1;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,0,0},{1,1,0},{0,0,0},{0,1,1},
   {0,0,0}};
   cout << (ob.shortestPath(v, 1));
}

입력

{{0,0,0},{1,1,0},{0,0,0},{0,1,1},{0,0,0}}