ウサギが箱を引っ張って移動させる最短時間を求めるC++プログラム

問題の概要

2つの座標 (x1, y1) と (x2, y2) が与えられます。ウサギは食べ物の入った箱を、長さ1単位のロープで引っ張って移動させます。

ウサギは箱を引っ張るとき、箱を自分の現在位置まで引き寄せ、その後同じ方向へ1単位だけ退避します。また、箱を引っ張らない状態であれば上下左右へ自由に1単位ずつ移動でき、このとき箱との距離が厳密に1単位である必要はありません。ただし、再び引っ張るためには箱の隣接するマスまで移動しなければなりません。ウサギは任意のマスからスタートでき、どの方向に1単位移動するにも1秒かかります。箱を出発位置から目的地まで移動させるのに必要な最小時間を求めましょう。

具体例

入力が x1 = 1、y1 = 1、x2 = 2、y2 = 2 の場合、出力は 4 となります。手順は以下のとおりです。

1. ウサギは点 (2, 1) からスタートします。
2. (3, 1) へ退避しながら箱を (2, 1) まで引き寄せます(1秒)。
3. 箱を引っ張らずに (3, 2) へ、さらに (2, 2) へ移動します(2秒)。
4. (2, 3) へ退避しながら箱を (2, 2) まで引き寄せます(1秒)。

こうして合計4秒で箱を目的地に運ぶことができます。

解法のアプローチ

この問題は、始点と終点の位置関係によって場合分けするとシンプルに解けます。

• x座標とy座標の両方が異なる場合(斜め方向への移動): マンハッタン距離 |x2 − x1| + |y2 − y1| に加えて、進行方向を変えるために箱の周りへ回り込む時間として2秒が余分にかかります。
• x座標またはy座標のどちらか一方のみが異なる場合(同一の直線上にある場合): 箱を一直線に引っ張り続けるだけでよいため、必要な時間は |x2 − x1| + |y2 − y1| だけで済みます。

これを擬似コードで表すと次のようになります。

s := 0
if x1 ≠ x2 かつ y1 ≠ y2 の場合:
    s := |x2 - x1| + |y2 - y1| + 2
それ以外の場合:
    s := |x2 - x1| + |y2 - y1|
return s

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
int solve(int x1, int y1, int x2, int y2){
    int s = 0;
    if (x1 != x2 && y1 != y2)
        s = abs(x2 - x1) + abs(y2 - y1) + 2;
    else
        s = abs(x2 - x1) + abs(y2 - y1);
    return s;
}
int main(){
    int x1 = 1;
    int y1 = 1;
    int x2 = 2;
    int y2 = 2;
    cout << solve(x1, y1, x2, y2) << endl;
}

入力

1, 1, 2, 2

出力

4

座標 (1, 1) から (2, 2) へは斜め方向への移動となるため、マンハッタン距離の2に回り込み時間の2秒を加えた4が出力されます。このように、移動方向の関係を見極めて場合分けすれば、O(1) の計算量で答えを求められます。