C++ですべてのキーを取得するための最短パス

A、Bなどの各ロックには、a、bなどのキーがあるため、ロックは大文字で同じ文字であり、キーは小文字で同じです。

すべてのキーを取得するには、最小の移動数を見つける必要があります。不可能な場合は、-1を返します。

したがって、入力が["@ .a。＃"、 "###。＃"、 "b.A.B"]の場合、出力は8

これを解決するには、次の手順に従います-

• n：=行数、m：=列数

• サイズ3の配列開始を定義します

• cnt：=0

• 初期化i：=0の場合、i

  • 初期化j：=0の場合、j

    • grid [i、j]が'@'と同じ場合、-

      • start [1]：=i、start [2]：=j

    • grid [i、j]> ='a'およびgrid[i、j] <='f'の場合、-

      • cnt：=cntとgrid[i、j]の最大値-'a' + 1

• 訪問した1セットを定義する

• req：=2 ^（cnt-1）

• 配列の1つのキューqを定義します

• qに開始を挿入

• 訪問先に開始を挿入

• レベル：=0

• （qが空ではない）間、-

  • sz：=qのサイズ

  • szがゼロ以外の場合、各反復後にszを減らし、-

    を実行します。

    • 配列currを定義します：=qのフロント要素

    • qから要素を削除

    • キー：=curr [0]

    • keyがreqと同じ場合、-

      • リターンレベル

    • x：=curr [1]、y：=curr [2]

    • prevKey：=key

    • 初期化i：=0の場合、i <4の場合、更新（iを1増やします）、実行-

      • nx：=x + dir [i、0]、ny：=y + dir [i、1]

      • キー：=prevKey

      • 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]-'A'のASCII）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"}

出力

8