C++で建物の中心座標と高さを全探索で求める方法

問題の概要

ある建物の中心座標を (xc, yc)、高さを h とします。中心座標と高さは直接わかりませんが、x 座標・y 座標とその地点の高度値 a を含む n 個の観測情報が与えられます。

座標 (x, y) における高度は、次の式で定義されます。

a(x, y) = max(h − |x − xc| − |y − yc|, 0)

この式から、建物の中心に近いほど高度が高くなり、一定以上離れると高度が 0 になることがわかります。配列 x には xi、配列 y には yi、配列 a には ai が格納されています。

たとえば、入力が n = 3、x = {3, 3, 2}、y = {4, 2, 3}、a = {6, 6, 6} の場合、出力は「3 3 7」になります。これは中心座標が (3, 3)、建物の高さが 7 であることを意味します。

解法のアプローチ

この問題は全探索(ブルートフォース)で解くことができます。座標の範囲が 0 以上 100 以下に制限されているため、考えられるすべての中心座標候補 (xc, yc) を試し、与えられた観測情報と矛盾しない組み合わせを見つけます。

各候補座標については、次の方針で整合性をチェックします。

• a[i] > 0 の場合： その点は建物の内部にあるため、「h = a[i] + k」(k は点 (x[i], y[i]) と (xc, yc) のマンハッタン距離)が常に成り立つはずです。複数の正の観測値から得られる h が一致しない場合は、その候補を除外します。
• a[i] = 0 の場合： その点は建物の外部にあるため、「h ≤ k」でなければなりません。この条件を満たさない候補も除外します。

計算量は O(101 × 101 × n) 程度であり、制約が小さいため十分高速に動作します。

アルゴリズムの手順

この問題を解くために、以下の手順に従います。

check := true
xc を 0 から 100 まで 1 ずつ増やしながら繰り返す:
    yc を 0 から 100 まで 1 ずつ増やしながら繰り返す:
        check := true
        mh := 2000000000
        h := -1
        i を 0 から n-1 まで 1 ずつ増やしながら繰り返す:
            k := |x[i] - xc| + |y[i] - yc|
            もし a[i] が 0 ならば:
                mh := min(mh, k)
            そうでなければ:
                もし h < 0 ならば:
                    h := a[i] + k
                そうでなく h ≠ a[i] + k ならば:
                    check := false
                    内側のループを抜ける
        もし h > mh ならば:
            check := false
            次の候補座標へスキップ
        もし check が真ならば:
            二重ループを抜ける
print(xc, yc, h)

C++ 実装例

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

#include <bits/stdc++.h>
using namespace std;

void solve(int n, vector<int> x, vector<int> y, vector<int> a){
   bool check = true;
   int xc, yc, h;
   for (xc = 0; xc <= 100; xc++) {
      for (yc = 0; yc <= 100; yc++) {
         check = true;
         int k, mh = 2e9;
         h = -1;
         for(int i = 0; i < n; i++) {
            k = abs(x[i] - xc) + abs(y[i] - yc);
            if (a[i] == 0) {
               mh = min(mh, k);
            } else {
               if (h < 0) {
                  h = a[i] + k;
               } else if (h != a[i] + k) {
                  check = false;
                  break;
               }
            }
         }
         if (h > mh) {
            check = false;
            continue;
         }
         if (check) {
            break;
         }
      }
      if (check) {
         break;
      }
   }
   cout << xc << " " << yc << " " << h;
}
int main() {
   int n = 3;
   vector<int> x = {3, 3, 2}, y = {4, 2, 3}, a = {6, 6, 6};
   solve(n, x, y, a);
   return 0;
}

入力例

3, {3, 3, 2}, {4, 2, 3}, {6, 6, 6}

出力例

3 3 7

このように、観測された高度情報をもとに全探索を行うことで、建物の中心座標 (3, 3) と高さ 7 を正しく求めることができました。