C++의 미로 III

<시간/>

빈 공간과 벽이 있는 미로가 있고 그 미로에도 공이 있다고 가정합니다. 공은 위(u), 아래(d), 왼쪽(l), 오른쪽(r) 방향으로 굴러 빈 공간을 통과할 수 있지만 벽에 부딪힐 때까지 계속 굴러갑니다. 공이 멈추면 다음 방향을 선택할 수 있습니다. 그 미로에도 구멍이 하나 있습니다. 공이 구멍으로 굴러 가면 구멍으로 떨어집니다.

따라서 공 위치, 구멍 위치 및 미로가 있는 경우 최단 거리를 이동하여 공이 어떻게 구멍에 떨어질 수 있는지 알아내야 합니다. 여기서 거리는 시작(제외)에서 홀(포함)까지 공이 이동한 빈 공간의 수로 정의됩니다.

'u', 'd', 'l' 및 'r'을 사용하여 이동 방향을 반환합니다. 여러 가지 다른 최단 방법이 있을 수 있기 때문에 출력은 사전식으로 가장 작은 방법이어야 합니다. 볼이 홀에 도달하지 못하면 "불가능"을 표시합니다.

여기서 미로는 이진 행렬로 표시됩니다. 1은 벽을 의미하고 0은 빈 공간을 의미합니다. 볼 및 홀 좌표는 행 및 열 인덱스로 표시됩니다.

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

C++의 미로 III

그러면 출력은 왼쪽으로 이동하면서 'lul'이 되고, 그 다음에는 왼쪽으로 올라가고, 다른 결과는 'ul'이 될 수 있고, 그 다음에는 왼쪽으로, 둘 다 길이가 6이지만 사전순으로 'lul'보다 작지는 않습니다.

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

Data라고 하는 하나의 데이터 유형을 정의합니다. 이것은 거리, 문자열 d 및 좌표 x,y를 취합니다.
크기의 배열 디렉토리 정의:4 x 2 :={{1, 0}, {0, - 1}, {0, 1}, { - 1, 0}}
크기의 배열 dirst 정의:4 :={'d', 'l', 'r', 'u'}
ok() 함수를 정의하면 x1, y1, x2, y2,
가 필요합니다.
x1이 x2와 같고 y1이 y2와 같으면 true를 반환
주요 방법에서 다음을 수행하십시오 -
n :=미로의 행 크기
m :=(n이 0이 아니면 미로의 열 크기, 그렇지 않으면 0)
하나의 우선순위 큐 pq 정의
(0, ball[0], ball[1], "")이 있는 새 데이터를 pq에 삽입
n x m 크기의 방문하는 하나의 2D 배열 정의
동안(pq가 비어 있지 않음) −
- curr :=pq의 최상위 요소
- x :=curr.x
- y :=curr.y
- dist :=curr.dist
- d :=curr.d
- ok(x, y, 구멍[0], 구멍[1])이면 -
  - 리턴 d
- 방문[x, y] :=참
- pq에서 요소 삭제
- k:=0 초기화의 경우 k − 4일 때 업데이트(k를 1만큼 증가), −
  - nx :=x, ny :=y
  - tempDist :=0
  - 동안 nx + dir[k, 0] =0 및 ny + dir[k, 1] =0 및 미로[nx + dir[k, 0], ny + dir[k, 1]]은 0, do -
    - nx :=nx + dir[k, 0]
    - ny :=ny + dir[k, 1]
    - (tempDist를 1만큼 증가)
    - ok(nx, ny, 구멍[0], 구멍[1])이면 -
      - 루프에서 나오세요
  - 방문[nx, ny]이 0이면 -
    - pq에 새 데이터(dist + tempDist, nx, ny, d + dirst[k]) 삽입
- "불가능" 반환

예시

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

#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
char dirst[4] = {'d', 'l', 'r', 'u'};
class Solution {
public:
   struct Data {
      int dist;
      string d;
      int x, y;
      Data(int a, int b, int c, string s) {
         d = s;
         dist = a;
         x = b;
         y = c;
      }
   };
   struct Comparator {
      bool operator()(Data a, Data b) {
         return a.dist != b.dist ? !(a.dist < b.dist) : !(a.d < b.d);
      }
   };
   bool ok(int x1, int y1, int x2, int y2) { return x1 == x2 && y1 == y2; }
   string findShortestWay(vector<vector<int>> &maze, vector<int>&ball,
      vector<int> &hole) {
         int n = maze.size();
         int m = n ? maze[0].size() : 0;
         priority_queue<vector<Data>, vector<Data>, Comparator> pq;
         pq.push(Data(0, ball[0], ball[1], ""));
         vector<vector<bool>> visited(n, vector<bool>(m));
         while (!pq.empty()) {
            Data curr = pq.top();
            int x = curr.x;
            int y = curr.y;
            int dist = curr.dist;
            string d = curr.d;
            if (ok(x, y, hole[0], hole[1])) {
               return d;
            }
            visited[x][y] = true;
            pq.pop();
            for (int k = 0; k < 4; k++) {
               int nx = x;
               int ny = y;
               int tempDist = 0;
               while (nx + dir[k][0] < n && nx + dir[k][0] >= 0 && ny + dir[k][1] < m && ny + dir[k][1] >= 0 && !maze[nx + dir[k][0]][ny + dir[k][1]]) {
                  nx += dir[k][0];
                  ny += dir[k][1];
                  tempDist++;
                  if (ok(nx, ny, hole[0], hole[1]))
                     break;
               }
               if (!visited[nx][ny]) {
                  pq.push(Data(dist + tempDist, nx, ny, d + dirst[k]));
               }
            }
         }
         return "impossible";
   }
};
main() {
   Solution ob;
   vector<vector<int>> v = {
      {0, 0, 0, 0, 0},
      {1, 1, 0, 0, 1},
      {0, 0, 0, 0, 0},
      {0, 1, 0, 0, 1},
      {0, 1, 0, 0, 0}};
   vector<int> v1 = {4, 3}, v2 = {0, 1};
   cout << (ob.findShortestWay(v, v1, v2));
}

입력

vector<vector<int>> v = {{0, 0, 0, 0, 0},
{1, 1, 0, 0, 1},
{0, 0, 0, 0, 0},
{0, 1, 0, 0, 1},
{0, 1, 0, 0, 0}};
vector<int> v1 = {4, 3}, v2 = {0, 1};

출력

lul