【C++】ロボットが(0,0)から(x,y)へ移動する際の最小ステップ数を求めるプログラム

問題概要

座標 (x, y) が与えられているとします。2次元グリッド上で、ロボットは初期位置 (0, 0) におり、目標地点 (x, y) への移動を目指しています。ロボットは1回のコマンドで「上」「下」「左」「右」のいずれかに移動するか、現在のマスにとどまる（待機する）ことができます。ここで、目的地に到達するまでに必要なコマンド数、つまりステップ数の最小値を求めることが課題です。

入力例と出力例

たとえば、入力が x = 3、y = 4 の場合、出力は 7 になります。

解法のアプローチ

この問題は、以下の式を使って答えを直接計算することで解けます。

return x + y + min(|x - y|, |x - y + 1|, |x - y - 1|)

つまり、基本となる「x + y」に対して、「|x − y|」「|x − y + 1|」「|x − y − 1|」という3つの絶対値の中で最も小さい値を加算したものが答えになります。abs() で絶対差を求め、min() を入れ子にすることで3つの候補の中から最小値を簡単に取り出せるのがポイントです。

C++による実装例

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

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

int solve(int x, int y) {
   return x + y + min(abs(x - y), min(abs(x - y + 1), abs(x - y - 1)));
}

int main() {
   int x = 3;
   int y = 4;
   cout << solve(x, y) << endl;
}

実行結果

入力

3, 4

出力

7

まとめ

このプログラムでは、solve 関数が座標の差を利用した計算式によって最小ステップ数を返します。main 関数から x = 3、y = 4 を渡すと、x + y = 7 に絶対差の最小値 0 が加わり、結果として 7 が出力されます。このように、グリッド上の移動問題では各軸の座標差に着目することで、シンプルな数式で最短手数を効率よく導出できます。