ロボットが最終位置に到達するまでの最小ステップ数を求めるC++プログラム

2つの座標 (x1, y1) と (x2, y2) があるとします。ロボットは現在点 (x1, y1) にいて、点 (x2, y2) へ移動したいと考えています。ロボットは1ステップごとに、周囲8方向（上下左右と斜め）の隣接するマスのいずれかに移動することができます。このとき、最終位置に到達するために必要な最小ステップ数を求めます。

例えば、入力が x1 = 3; y1 = 4; x2 = 6; y2 = 1; の場合、出力は 3 になります。その様子は以下の図の通りです。

解き方

この問題を解くには、次のステップに従います。

return max(|x2 - x1|, |y2 - y1|)

なぜこれで正しく求まるのか

ロボットは8方向に移動できるため、1ステップでX方向とY方向の両方を同時に1マスずつ進むことが可能です。したがって、必要なステップ数はX方向の移動距離 |x2 − x1| とY方向の移動距離 |y2 − y1| のうち大きい方に一致します。これは「チェビシェフ距離」として知られる考え方で、斜め移動が許可されているグリッド上の最短経路問題ではよく使われる手法です。

実装例

理解を深めるために、以下のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(int x1, int y1, int x2, int y2){
    return max(abs(x2 - x1), abs(y2 - y1));
}
int main(){
    int x1 = 3;
    int y1 = 4;
    int x2 = 6;
    int y2 = 1;
    cout << solve(x1, y1, x2, y2) << endl;
}

入力

3, 4, 6, 1

出力

3