C++で解く「Maze III」：ボールを最短距離で穴に落とすアルゴリズム

問題の概要

空きスペースと壁からなる迷路の中に、ボールが1つ置かれています。ボールは空きスペース上を上（u）・下（d）・左（l）・右（r）のいずれかの方向に転がって移動できますが、壁にぶつかるまで停止しません。ボールが停止した時点で、次の方向を選択できます。また、迷路内には穴（hole）が1つあり、ボールが穴の位置まで転がると、その穴に落ちます。

ボールの初期位置・穴の位置・迷路の情報が与えられたとき、ボールを最短距離で穴に落とすための移動手順を求めます。ここでいう距離とは、スタート地点（含まない）から穴（含む）までにボールが通過した空きスペースの数として定義されます。

移動方向は「u」「d」「l」「r」の文字列として返します。最短経路が複数存在する場合は、辞書順で最小となるものを出力してください。ボールが穴に到達できない場合は「impossible」と表示します。

迷路は0と1からなる二次元行列で表現され、1が壁、0が空きスペースを意味します。ボールと穴の座標は、それぞれ行と列のインデックスで与えられます。

たとえば、次のような入力が与えられたとします。

この場合の出力は「lul」（左→上→左）になります。同じ長さ6となる別の経路「ul」（上→左）も存在しますが、「ul」は「lul」よりも辞書順で大きいため、採用されるのは「lul」の方です。

解法のアプローチ

この問題は、ダイクストラ法の考え方を応用して解きます。優先度付きキュー（priority queue）を使い、距離が短い状態から順に探索することで、最短かつ辞書順最小の経路を効率よく見つけられます。具体的な手順は以下の通りです。

• Data型を定義します。この型は距離（dist）、移動方向の文字列（d）、座標（x, y）を保持します。
• サイズ4×2の配列dirを {{1, 0}, {0, -1}, {0, 1}, {-1, 0}} として定義します。
• サイズ4の配列dirstを {'d', 'l', 'r', 'u'} として定義します。
• 関数ok()を定義します。引数はx1, y1, x2, y2です。
• x1がx2と等しく、かつy1がy2と等しい場合にtrueを返します。

mainメソッドでは以下の処理を行います。

• n := 迷路の行数
• m := （nが0でなければ迷路の列数、そうでなければ0）
• 優先度付きキューpqを定義します。
• (0, ball[0], ball[1], "") を持つ新しいDataをpqに挿入します。
• サイズn×mの二次元配列visitedを定義します。
• pqが空になるまで、以下を繰り返します。
  • curr := pqの先頭要素
  • x := curr.x、y := curr.y、dist := curr.dist、d := curr.d
  • ok(x, y, hole[0], hole[1])が成り立つ場合、dを返します。
  • visited[x][y] := true とし、pqから先頭要素を削除します。
  • k := 0 から k < 4 の間、kを1ずつ増やしながら以下を繰り返します。
    • nx := x、ny := y、tempDist := 0
    • nx + dir[k][0] と ny + dir[k][1] が迷路の範囲内であり、かつ maze[nx + dir[k][0]][ny + dir[k][1]] が0である間、以下を繰り返します。
      • nx := nx + dir[k][0]、ny := ny + dir[k][1]
      • tempDistを1増やします。
      • ok(nx, ny, hole[0], hole[1])が成り立てば、ループを抜けます。
    • visited[nx][ny]がfalseの場合、新しいData(dist + tempDist, nx, ny, d + dirst[k])をpqに挿入します。
• すべての探索が終わったら「impossible」を返します。

C++実装例

理解を深めるために、以下の実装例を見てみましょう。

#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