C++で解く「すべての鍵を取得する最短経路」問題：BFSとビットマスクの活用法

問題の概要

グリッド上で展開されるパズル問題を考えます。グリッドには以下の記号が使われています。

• . … 空きマス(自由に移動可能)
• # … 壁(通行不可)
• @ … スタート地点
• a, b, c … … 鍵(マスを通過すると自動的に拾う)
• A, B, C … … 鍵穴(ロック)。対応する鍵を持っていないと通過できない

スタート地点から出発し、1回の移動で上下左右4方向のいずれかに1マス進みます。グリッドの外に出ることはできず、壁が進路を妨げます。鍵のマスを通過するとその鍵を拾い、対応する鍵を所持していない限りロックのマスは通れません。

鍵穴「A」には鍵「a」、鍵穴「B」には鍵「b」のように、大文字がロック、同じ文字の小文字が対応する鍵を表します。

求めるのは、すべての鍵を集めるまでの最小移動回数です。すべての鍵を集めることが不可能な場合は -1 を返します。

例えば、入力が ["@.a.#","###.#","b.A.B"] の場合、出力は 8 となります。

解法のアプローチ

この問題は幅優先探索(BFS)とビットマスクを組み合わせて効率的に解けます。鍵の所持状態をビット列で管理し、「(鍵の状態, 座標)」の組み合わせを1つの状態として扱うことで、同じマスでも鍵の所持状況が異なれば別の状態として探索できます。

アルゴリズムの手順

1. 行数 n、列数 m を取得します。
2. サイズ3の配列 start を用意します。
3. cnt := 0 で初期化します。
4. グリッド全体を走査します。
   • grid[i][j] が '@' なら、start[1] = i、start[2] = j とします。
   • grid[i][j] が 'a'〜'f' の範囲なら、cnt = max(cnt, grid[i][j] - 'a' + 1) とします。
5. 訪問済み状態を記録するセット visited を定義します。
6. req := 2^cnt - 1(すべての鍵を所持した状態を表すビットマスク)とします。
7. 配列を要素とするキュー q を定義し、start を追加して visited に登録します。
8. level := 0 とします。
9. キューが空になるまで以下を繰り返します。
   • sz := キューのサイズとします。
   • sz 回だけ以下を処理します。
     • curr := キューの先頭要素を取り出します。
     • key := curr[0] とし、key が req と等しければ level を返します。
     • x := curr[1]、y := curr[2]、prevKey := key とします。
     • 4方向それぞれについて以下を確認します。
       • nx := x + dir[i][0]、ny := y + dir[i][1] を計算し、key を prevKey に戻します。
       • (nx, ny) がグリッド内の場合:
         • grid[nx][ny] が '#' なら、次の反復へスキップします。
         • grid[nx][ny] が 'a'〜'f' なら、key |= (1 << (grid[nx][ny] - 'a')) でその鍵を取得したことにします。
         • grid[nx][ny] が 'A'〜'F' で、対応する鍵のビットが立っていなければ、スキップします。
         • 状態 {key, nx, ny} が visited に含まれていなければ、キューと visited に追加します。
   • level を1増やします。
10. キューが空になっても条件を満たせなければ、-1 を返します。

実装例(C++)

以下は上記のアルゴリズムをC++で実装した例です。

#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

計算量の目安

鍵は最大6個(a〜f)であるため、鍵の所持状態は最大 2^6 = 64 通りです。グリッドのマス数を N、鍵の数を K とすると、状態の総数は高々 N × 2^K となり、BFSは各状態を1回ずつ処理するので、時間計算量・空間計算量はともに O(N × 2^K) となります。

まとめ

本問題のポイントは、単なる座標だけでなく「鍵の所持状態」も含めた状態管理を行う点です。ビットマスクを活用することで、鍵の取得状況をコンパクトに表現でき、BFSと組み合わせることで最短移動回数を効率的に求められます。迷路探索とビット演算を組み合わせる典型的なテクニックなので、ぜひマスターしておきましょう。