C++에서 모든 키를 가져오는 최단 경로

그리드가 있다고 가정합니다. 기호가 거의 없습니다. "." 는 빈 셀, "#"은 벽, "@"는 시작점, ("a", "b", ...) 모두 키, ("A", "B", ...) ) 모두 자물쇠입니다. 출발점에서 출발하여 4방향(좌,우,상,하) 중 하나로 한 칸씩 걷는 것이 1동작이다. 우리는 그리드 밖으로 나가지 않을 것이며 우리의 길을 막는 벽이 있습니다. 열쇠 위를 걸어가면 열쇠를 줍습니다. 해당 열쇠가 없으면 자물쇠를 넘을 수 없습니다.

A, B 등의 각 자물쇠에 대해, b 등의 키가 있으므로 자물쇠는 대문자와 동일하고 키는 소문자와 동일합니다.

모든 키를 얻으려면 가장 적은 수의 이동을 찾아야 합니다. 불가능한 경우 -1을 반환합니다.

따라서 입력이 ["@.a.#",###.#","b.A.B"]와 같으면 출력은 8

이 됩니다.

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

n :=행 수, m :=열 수
크기가 3인 배열 시작을 정의합니다.
cnt :=0
initialize i :=0의 경우, i
- j 초기화의 경우:=0, j
  - grid[i, j]가 '@'와 같으면 -
    - 시작[1] :=나, 시작[2] :=j
  - grid[i, j]>='a'이고 grid[i, j] <='f'이면 -
    - cnt :=cnt 및 grid[i, j]의 최대값 - 'a' + 1
방문한 한 세트 정의
요구사항 :=2^(cnt - 1)
배열의 하나의 대기열 q 정의
q에 시작 삽입
방문에 시작 삽입
레벨 :=0
동안(q가 비어 있지 않음) -
를 수행합니다.
- sz :=q의 크기
- sz가 0이 아닌 동안 각 반복 후에 sz를 감소시키고 -
  - 배열 정의 curr :=q의 앞 요소
  - q에서 요소 삭제
  - 키 :=curr[0]
  - 키가 req와 같으면 -
    - 반환 수준
  - x :=curr[1], y :=curr[2]
  - prevKey :=키
  - initialize i :=0의 경우, i <4일 때 업데이트(i를 1만큼 증가), 수행 -
    - nx :=x + dir[i, 0], ny :=y + dir[i, 1]
    - 키 :=이전 키
    - nx>=0이고 ny>=0이고 nx
      - grid[nx, ny]가 '#'과 같으면 -
        
        다음 부분은 무시하고 다음 반복으로 건너뜁니다.
      - grid[nx, ny]>='a'이고 grid[nx, ny] <='f'이면 -
        
        key :=key OR (2^(grid[nx, ny] - 'a'의 ASCII))
      - grid[nx, ny]>='A'이고 grid[nx, ny] <='F'이면 -
        
        (오른쪽으로 이동 키(grid[nx, ny] - ASCII of 'A') timesAND 1)가 0과 같으면 -
        
        다음 부분은 무시하고 다음 반복으로 건너뜁니다.
      - 배열 상태 정의({ key, nx, ny })
      - 상태가 방문 중인 경우 -
        
        다음 부분은 무시하고 다음 반복으로 건너뜁니다.
      - 상태를 q
        에 삽입
      - 방문 상태 삽입
- (레벨 1 증가)
반환 -1

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

예

#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
class Solution {
   public:
   int shortestPathAllKeys(vector<string>& grid) {
      int n = grid.size();
      int m = grid[0].size();
      vector<int> start(3);
      int cnt = 0;
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < m; j++) {
            if (grid[i][j] == '@') {
               start[1] = i;
               start[2] = j;
            }
            if (grid[i][j] >= 'a' && grid[i][j] <= 'f') {
               cnt = max(cnt, grid[i][j] - 'a' + 1);
            }
         }
      }
      set<vector<int> > visited;
      int req = (1 << cnt) - 1;
      queue<vector<int> > q;
      q.push(start);
      visited.insert(start);
      int level = 0;
      while (!q.empty()) {
         int sz = q.size();
         while (sz--) {
            vector<int> curr = q.front();
            q.pop();
            int key = curr[0];
            if (key == req)
            return level;
            int x = curr[1];
            int y = curr[2];
            int nx, ny;
            int prevKey = key;
            for (int i = 0; i < 4; i++) {
               nx = x + dir[i][0];
               ny = y + dir[i][1];
               key = prevKey;
               if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                  if (grid[nx][ny] == '#')
                  continue;
                  if (grid[nx][ny] >= 'a' && grid[nx][ny] <=
                  'f') {
                     key |= (1 << (grid[nx][ny] - 'a'));
                  }
                  if (grid[nx][ny] >= 'A' && grid[nx][ny] <=
                  'F') {
                     if (((key >> (grid[nx][ny] - 'A')) & 1)
                     == 0)
                     continue;
                  }
                  vector<int> state({ key, nx, ny });
                  if (visited.count(state))
                  continue;
                  q.push(state);
                  visited.insert(state);
               }
            }
         }
         level++;
      }
      return -1;
   }
};
main(){
   Solution ob;
   vector<string> v = {"@.a.#","###.#","b.A.B"};
   cout << (ob.shortestPathAllKeys(v));
}

입력

{"@.a.#","###.#","b.A.B"}