C++で解く「幽霊からの脱出」問題 ― マンハッタン距離による判定アルゴリズム

問題概要

簡略化されたパックマン風のゲームを考えてみましょう。プレイヤーは点 (0, 0) からスタートし、目的地は (target[0], target[1]) です。マップ上には複数の幽霊がおり、i 番目の幽霊は (ghosts[i][0], ghosts[i][1]) からスタートします。

各ターンで、自分とすべての幽霊は同時に、北・東・西・南の4方向のいずれかに1単位ずつ移動できます(移動しない選択も含まれます)。幽霊がどのように動こうとも、自分がどの幽霊よりも先に目的地へ到達できれば脱出成功です。ただし、幽霊と同じマスに同時に到達した場合は脱出とはみなされません。脱出が可能なら true を返してください。

例えば、入力が [[1,0], [0,3]] でターゲットが [0,1] の場合、結果は true になります。これは、時刻 1 で直接目的地 (0, 1) に到達できる一方、(1, 0) や (0, 3) にいる幽霊にはどう動いても追いつけないためです。

解法のアプローチ

この問題の鍵となるのはマンハッタン距離です。グリッド上では、任意の2点間の最短移動距離はマンハッタン距離で表されるため、以下の手順で判定できます。

• me := |target[1]| + |target[0]| … 自分がスタート地点から目的地へ到達するのに必要なターン数
• x := 0
• i を 0 から幽霊配列のサイズ − 1 までループ
  • x := |ghosts[i][0] − target[0]| + |ghosts[i][1] − target[1]| … 各幽霊が目的地へ到達するのに必要なターン数
  • x <= me の場合、false を返す(その幽霊は先に、または同時に目的地へ到達できる)
• true を返す

直感的に説明すると、幽霊は自分の動きに関係なく最短経路で目的地へ向かえるため、自分より早く(または同じタイミングで)目的地に着ける幽霊が一匹でもいれば、その幽霊は目的地で待ち伏せできてしまいます。逆に、すべての幽霊が自分より遠い位置にいれば、相手がどんな手を選んでも自分が必ず先着できるため、確実に脱出可能です。

C++実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {
      int me = abs(target[1]) + abs(target[0]);
      int x = 0;
      for(int i = 0; i < ghosts.size(); i++){
         x = abs(ghosts[i][0] - target[0]) + abs(ghosts[i][1] - target[1]);
         if(x <= me) return false;
      }
      return true;
   }
};
main(){
   vector<vector<int>> v1 = {{1,0}, {0,3}};
   vector<int> v2 = {0,1};
   Solution ob;
   cout << (ob.escapeGhosts(v1, v2));
}

入力

[[1,0],[0,3]]
[0,1]

出力

1

この実装では、自分の目的地までのマンハッタン距離と各幽霊の目的地までのマンハッタン距離を単純に比較しているだけです。時間計算量は O(n)(n は幽霊の数)、空間計算量は O(1) と非常に効率的で、追加のデータ構造も不要です。