【C++】グリッド上のオブジェクトを発見するのに必要なスキャン回数を求めるコード

ここでは、m × n のサイズを持つグリッドが与えられていると仮定します。あるオブジェクトがセル (ix, iy) に配置されており、開始位置 (sx, sy) からスキャンを実行して、このオブジェクトを発見することが目的です。

スキャンのアルゴリズムは、グリッド上のセル (i, j) に位置しているとき、i 行目と j 列目全体をスキャンします。オブジェクトが見つかった時点でスキャンは終了し、まだ見つからない場合は、ポインタがセル (i + 1, j + 1) に移動して同じ要領で再度スキャンを行います。この処理を、オブジェクトが見つかるまで繰り返します。各位置情報が与えられたとき、アルゴリズムがオブジェクトを発見するまでに何回のスキャンが必要かを求めましょう。

たとえば、入力が n = 20、m = 20、sx = 3、sy = 2、ix = 12、iy = 4 である場合、出力は 2 となります。

解き方の手順

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

• t1 := （sx <= ix であれば ix − sx、そうでなければ 2 * n − ix − sx）
• t2 := （sy <= iy であれば iy − sy、そうでなければ 2 * m − iy − sy）
• t1 と t2 のうち小さい方の値を出力する

ポイントは、スキャンポインタが対角方向へ進んでいくという仕組みを利用することです。行方向と列方向のそれぞれについて、オブジェクトが存在する行・列に到達するまでの移動回数を計算します。どちらか早い段階でオブジェクトが検知されるため、両者の最小値が答えとなります。

C++による実装例

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

#include <bits/stdc++.h>
using namespace std;
#define N 100
void solve(int n, int m, int sx, int sy, int ix, int iy) {
    int t1 = (sx <= ix ? ix - sx : 2 * n - ix - sx);
    int t2 = (sy <= iy ? iy - sy : 2 * m - iy - sy);
    cout<< min(t1, t2);
}
int main() {
    int n = 20, m = 20, sx = 3, sy = 2 , ix = 12, iy = 4;
    solve(n, m, sx, sy, ix, iy);
    return 0;
}

入力

20, 20, 3, 2 , 12, 4

出力

2

このように、開始位置 (3, 2) からスキャンを開始すると、わずか 2 回のスキャンでオブジェクト (12, 4) を発見できることが確認できます。行・列それぞれの到達ステップ数を比較するだけのシンプルな計算で答えが得られるため、非常に効率的なアプローチといえるでしょう。