C++의 미로 II

<시간/>

빈 공간과 벽이 있는 미로에 공이 있다고 가정합니다. 이제 공은 위, 아래, 왼쪽 또는 오른쪽과 같은 방향으로 굴러 빈 경로를 통과할 수 있지만 벽에 부딪힐 때까지 구르는 것을 멈추지 않습니다. 공이 멈추면 다음 방향을 선택할 수 있습니다.

우리는 공의 시작 위치, 목적지, 미로를 찾아야 하고, 공이 목적지에 멈추는 최단 거리를 찾아야 합니다. 여기서 거리는 실제로 공으로 덮인 빈 셀의 수로 정의됩니다(시작 위치를 포함한 시작 위치 제외). 목적지에서 공을 멈출 수 없으면 -1을 반환합니다.

미로는 하나의 2D 배열로 표현됩니다. 여기서 1은 벽을 나타내고 0은 빈 공간을 나타냅니다. 미로의 경계는 모두 벽입니다. 시작 및 대상 좌표는 행 및 열 인덱스로 표시됩니다.

따라서 입력이 2D 배열로 표현되는 미로와 같은 경우

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

시작 위치가 (0, 4) 목적지 위치가 (4, 4)이면 출력은 12가 됩니다. 한 가지 가능한 방법은 다음과 같습니다. 왼쪽에서 아래로 왼쪽에서 오른쪽에서 오른쪽에서 아래로. (1+1+3+1+2+2+2) =12

C++의 미로 II

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

n :=행 개수, m :=열 개수
ret :=무한대
n x m 차수의 2D 배열 거리 정의
하나의 대기열 정의 q
q에 시작 삽입
거리[시작[0], 시작[1]] :=0
동안(q가 비어 있지 않음) -
를 수행합니다.
- curr :=q의 첫 번째 요소
- q에서 요소 삭제
- x :=curr[0], y :=curr[1]
- x가 대상[0]과 같고 y가 대상[1]과 같으면 -
  - ret :=ret 및 dist[x, y]
    의 최소값
- currDist :=dist[x, y]
- tempDist :=0
- 나는 :=x
- 동안 (i + 1
  - (i를 1씩 증가)
  - (tempDist를 1만큼 증가)
- currDist + tempDist
  - dist[i, y] :=currDist + tempDist
  - q에 { i, y } 삽입
- 나는 :=x
- tempDist :=0
- 동안 (i - 1>=0이고 grid[i - 1, y]는 0임), −
  - (tempDist를 1만큼 증가)
  - (i를 1 감소)
- currDist + tempDist *lt; dist[i, y], 다음 -
  - dist[i, y] :=currDist + tempDist
  - q에 { i, y } 삽입
- 나는 :=y
- tempDist :=0
- 동안 (i - 1>=0이고 grid[x, i - 1]은 0임) −
  - (i를 1 감소)
  - (tempDist를 1만큼 증가)
- currDist + tempDist
  - dist[x, i] :=currDist + tempDist
  - q에 { x, i } 삽입
- 나는 :=y
- tempDist :=0
- 동안 (i + 1
  - (i를 1씩 증가)
  - (tempDist를 1만큼 증가)
- currDist + tempDist
  - dist[x, i] :=currDist + tempDist
  - q에 { x, i } 삽입

return (ret가 inf와 같으면 -1, 그렇지 않으면 ret)

예시

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int shortestDistance(vector<vector<int<>& grid, vector<int<& start, vector<int<& destination) {
   int n = grid.size();
   int m = n? grid[0].size() : 0;
   int ret = INT_MAX;
   vector < vector <int< > dist(n, vector <int<(m, INT_MAX));
   queue < vector <int< > q;
   q.push(start);
   dist[start[0]][start[1]] = 0;
   while(!q.empty()){
      vector <int< curr = q.front();
      q.pop();
      int x = curr[0];
      int y = curr[1];
      if(x == destination[0] && y == destination[1]){
         ret = min(ret, dist[x][y]);
      }
      int currDist = dist[x][y];
      int tempDist = 0;
      int i = x;
      while(i + 1 < n && !grid[i + 1][y]){
         i++;
         tempDist++;
      }
      if(currDist + tempDist < dist[i][y]){
         dist[i][y] = currDist + tempDist;
         q.push({i, y});
      }
      i = x;
      tempDist = 0;
      while(i - 1 >= 0 && !grid[i - 1][y]){
         tempDist++;
         i--;
      }
      if(currDist + tempDist < dist[i][y]){
         dist[i][y] = currDist + tempDist;
         q.push({i, y});
      }
      i = y;
      tempDist = 0;
      while(i - 1 >= 0 && !grid[x][i - 1]){
         i--;
         tempDist++;
      }
      if(currDist + tempDist < dist[x][i]){
         dist[x][i] = currDist + tempDist;
         q.push({x, i});
      }
      i = y;
      tempDist = 0;
      while(i + 1 < m && !grid[x][i + 1]){
         i++;
         tempDist++;
      }
      if(currDist + tempDist < dist[x][i]){
         dist[x][i] = currDist + tempDist;
         q.push({x, i});
      }
   }
   return ret == INT_MAX ? - 1 : ret;
};
main(){
   Solution ob;
   vector<vector<int<> v = {{0,0,1,0,0},{0,0,0,0,0},{0,0,0,1,0},{1,1,0,1,1},{0,0,0,0,0}};
   vector<int< v1 = {0,4}, v2 = {4,4};
   cout << (ob.shortestDistance(v, v1, v2));
}

입력

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