C++で解く！ロボットがグリッド上の目的地セルへ到達するための最小ジャンプ回数を求める方法

h × w のサイズを持つグリッドを考えてみましょう。このグリッドは2次元配列「initGrid」で表され、各セルは「#」または「.」のいずれかで構成されています。「#」はそのセルに障害物があることを意味し、「.」はそのセルを通って移動できることを示します。

ここで、行番号 x・列番号 y のセル c にロボットを配置します。ロボットは、行番号 p・列番号 q にある別のセル d へ移動しなければなりません。セル c と d の座標は、いずれも整数ペアとして与えられます。

ロボットは、以下のルールに従ってセル間を移動できます。

• 移動先のセルが現在いるセルの上下左右に隣接している場合、歩いて移動できます。

• 現在位置を中心とする5×5の範囲内にある任意のセルへジャンプできます。

• 障害物のあるセルへは移動できず、グリッドの外に出ることもできません。

私たちの課題は、目的地に到達するまでに必要なジャンプの回数を求めることです。

たとえば、入力が h = 4、w = 4、c = {2, 1}、d = {4, 4}、initGrid = {"#...", ".##.", "...#", "..#."} のとき、出力は 1 になります。ロボットはジャンプを1回行うだけで目的地へ到達できるためです。

解法のアプローチ（0-1 BFS）

この問題は「0-1 BFS」と呼ばれる手法で効率的に解けます。隣接セルへの歩行をコスト0、ジャンプをコスト1と考えると、これは辺の重みが0か1のみのグラフ上の最短経路問題に帰着できます。通常のBFSの代わりに両端キュー（deque）を使用し、コスト0の移動ではキューの先頭に、コスト1の移動では末尾にノードを追加することで、常に距離の昇順で探索を進められます。

具体的な手順は以下の通りです。

N := 100
整数ペア s と t を定義
サイズ N の配列 grid を定義
サイズ N × N の配列 dst を定義
整数 a, b, e を持つ構造体 node を定義

関数 check(a, b) を定義:
    return a >= 0 AND a < h AND b >= 0 AND b < w

関数 bfs(a, b) を定義:
    i := 0 とし、i < h の間 i を 1 ずつ増やす:
        j := 0 とし、j < w の間 j を 1 ずつ増やす:
            dst[i][j] := 無限大
    dst[a][b] := 0
    両端キュー doubleq を用意する
    ノード {a, b, dst[a][b]} を doubleq の末尾に追加
    doubleq が空でない間、以下を繰り返す:
        nd := doubleq の先頭要素
        もし nd の e の値 > dst[nd の a の値][nd の b の値] なら:
            以降をスキップして次の反復へ
        diffx := -2 とし、diffx <= 2 の間 diffx を 1 ずつ増やす:
            diffy := -2 とし、diffy <= 2 の間 diffy を 1 ずつ増やす:
                tm := |diffx| + |diffy|
                nx := nd の a の値 + diffx、ny := nd の b の値 + diffy
                もし check(nx, ny) かつ grid[nx][ny] が '.' と等しいなら:
                    w := (tm > 1 なら 1、そうでなければ 0)
                    もし dst[nd の a の値][nd の b の値] + w < dst[nx][ny] なら:
                        dst[nx][ny] := dst[nd の a の値][nd の b の値] + w
                        もし w が 0 と等しいなら:
                            ノード {nx, ny, dst[nx][ny]} を doubleq の先頭に追加
                        そうでなければ:
                            ノード {nx, ny, dst[nx][ny]} を doubleq の末尾に追加

s := c
t := d
s の第1要素と第2要素をそれぞれ 1 減らす
t の第1要素と第2要素をそれぞれ 1 減らす
i := 0 とし、i < h の間 i を 1 ずつ増やす:
    grid[i] := initGrid[i]
bfs(s の第1要素, s の第2要素) を呼び出す
dst[t の第1要素][t の第2要素] が無限大と等しい場合は -1 を、
そうでなければその値を出力する

実装例

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

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
#define N 100
int h, w;
pair<int, int> s, t;
string grid[N];
int dst[N][N];
struct node {
   int a, b, e;
};
bool check(int a, int b) {
   return a >= 0 && a < h && b >= 0 && b < w;
}
void bfs(int a, int b) {
   for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++)
         dst[i][j] = INF;
   }
   dst[a][b] = 0;
   deque<node> doubleq;
   doubleq.push_back({a, b, dst[a][b]});

   while (!doubleq.empty()) {
      node nd = doubleq.front();
      doubleq.pop_front();
      if (nd.e > dst[nd.a][nd.b])
         continue;
      for (int diffx = -2; diffx <= 2; diffx++) {
         for (int diffy = -2; diffy <= 2; diffy++) {
            int tm = abs(diffx) + abs(diffy);
            int nx = nd.a + diffx, ny = nd.b + diffy;
            if (check(nx, ny) && grid[nx][ny] == '.') {
               int w = (tm > 1) ? 1 : 0;
               if (dst[nd.a][nd.b] + w < dst[nx][ny]) {
                  dst[nx][ny] = dst[nd.a][nd.b] + w;
                  if (w == 0)
                     doubleq.push_front({nx, ny, dst[nx][ny]});
                  else
                     doubleq.push_back({nx, ny, dst[nx][ny]});
               }
            }
         }
      }
   }
}
void solve(pair<int,int> c, pair<int, int> d, string initGrid[]){
   s = c;
   t = d;
   s.first--, s.second--, t.first--, t.second--;
   for(int i = 0; i < h; i++)
      grid[i] = initGrid[i];
   bfs(s.first, s.second);
   cout << (dst[t.first][t.second] == INF ? -1 :
      dst[t.first][t.second]) << '\n';
}
int main() {
   h = 4, w = 4;
   pair<int,int> c = {2, 1}, d = {4, 4};
   string initGrid[] = {"#...", ".##.", "...#", "..#."};
   solve(c, d, initGrid);
   return 0;
}

入力

4, 4, {2, 1}, {4, 4}, {"#...", ".##.", "...#", "..#."}

出力

1

アルゴリズムのポイント

• コストの判定： 移動量のマンハッタン距離 tm が1以下なら「歩行」（コスト0）、2以上なら「ジャンプ」（コスト1）として扱います。
• 探索の効率化： 既により良い距離が記録されているノードはスキップすることで、無駄な再探索を防いでいます。
• 計算量： 各セルから最大25方向を調べるため、計算量は O(h × w × 25) に抑えられます。
• 到達不可能な場合： 目的地の距離が無限大のままなら、到達不能として -1 を出力します。