とても重たくて大変な問題。いろんな整理の仕方があると思う。
問題概要
下図のように、座標平面が 1 x 2 の長方形に区切られている。
座標 から座標
へと至るまでに、通過する必要のある長方形の境界の個数の最小値を求めよ。

制約
考えたこと
この手の問題は、スタート地点が原点になるように平行移動できれば、考えやすくなる。その際には、ゴール地点の 座標が正である方が考えやすいので、適宜 swap して、あらかじめ
となるようにすることにした。
スタートが原点になるようにするために、まず、スタートを または
に移るように平行移動することにした。具体的には、
- スタートとゴールの座標に対して、ともに
を足す
- スタートとゴールの座標に対して、ともに
を足す
- スタートとゴールの座標に対して、ともに
を足す
- スタートとゴールの座標に対して、ともに
を足す
- スタートとゴールの座標に対して、ともに
を足す
- スタートとゴールの座標に対して、ともに
を足す
という操作を繰り返すことを想定すればよい。最後に、スタート地点が である場合には
としても変わらないことを利用する。
スタートからゴールへ
座標 からスタートして、y 座標が
となる位置まで移動する際に、
方向の境界を通ることなく、到達できる x 座標を考えよう。
x 座標が 以上
以下
については、 方向の境界通過のみで到達できる。
がこの範囲におさまる場合は、答えは
となる。
がこの範囲におさまらない場合は、x 座標方向に通過する必要のある境界の個数を求めればよい。
コード
#include <bits/stdc++.h> using namespace std; int main() { // スタート地点を (0, 0) にするような調整を行う long long sx, sy, tx, ty; cin >> sx >> sy >> tx >> ty; if (sy > ty) swap(sx, tx), swap(sy, ty); sx -= sy, tx -= sy, ty -= sy, sy = 0; if (sx % 2 == 0) tx -= sx, sx = 0; else tx -= (sx - 1), sx = 0; // x 軸方向の移動距離を求める long long dx = 0; if (tx > ty + 1) tx -= ty, dx = tx / 2; else if (tx < -ty) tx += ty, dx = (-tx + 1) / 2; // y 軸方向の移動距離 (ty) を足す long long res = dx + ty; cout << res << endl; }