問題概要

時刻 $t$ に座標 $(x, y)$ にいるとき、以下のいずれかの行動をすることができる。

$x$ が偶数または $t$ が偶数のとき、時刻 $t+1$ に $(x+1, y)$ に移動する
$x$ が奇数または $t$ が偶数のとき、時刻 $t+1$ に $(x-1, y)$ に移動する
$y$ が偶数または $t$ が奇数のとき、時刻 $t+1$ に $(x, y+1)$ に移動する
$y$ が奇数または $t$ が奇数のとき、時刻 $t+1$ に $(x, y-1)$ に移動する

時刻 0 に座標 $(s_{x}, s_{y})$ にいて、座標 $(g_{x}, g_{y})$ を目指したい。最短でたどりつく時刻はいつになるか？

制約

$0 \le s_{x}, s_{y}, g_{x}, g_{y} \le 10^{18}$

考えたこと

$X = |s_{x} - g_{x}|$ 、 $Y = |s_{y} - g_{y}|$ とする。色々手を動かしていると、割と多くの場合で $X + Y$ で到達できることがわかる。どういうときにそれができるのかを色々考えてみる。

まず一つ言えるのは、斜め 45 度方向への移動であれば、任意の時刻・座標からでも、適切にジグザグに進むことができる。

もう一つ言えるのは、

「 $x$ が偶数かつ $t$ が奇数」という状態を作れば、x 軸正方向に無限に進める
「 $x$ が奇数かつ $t$ が奇数」という状態を作れば、x 軸負方向に無限に進める
「 $y$ が偶数かつ $t$ が偶数」という状態を作れば、y 軸正方向に無限に進める
「 $y$ が奇数かつ $t$ が偶数」という状態を作れば、y 軸負方向に無限に進める

以上を踏まえると、まず $s_{x} \neq g_{x}$ かつ $s_{y} \neq g_{y}$ である場合は、適切な位置合わせを行うことで、進みたい方向に無限に進める状態になる。そしてそれによって「斜め 45 度移動で到達できる状態」を作ってあげれば、到達できる。つまり、 $s_{x} \neq g_{x}$ かつ $s_{y} \neq g_{y}$ である場合には、 $X + Y$ で到達できる。

残りは丁寧に場合分けする。

sx = gx のとき

$s_{y}$ が偶数のとき、初期状態から y 軸正方向には無限に進めるが、y 軸負方向に進むなら 1 秒待つ必要がある。
$s_{y}$ が奇数のとき、初期状態から y 軸負方向には無限に進めるが、y 軸正方向に進むなら 1 秒待つ必要がある。

sy = gy のとき

$s_{x}$ が偶数のとき、初期状態から x 軸負方向には無限に進める。 $s_{x} + 1$ にも 1 秒で行ける。それ以外はどこかで 1 秒待つ必要がある。
$s_{x}$ が奇数のとき、初期状態から x 軸正方向には無限に進める。 $s_{x} - 1$ にも 1 秒で行ける。それ以外はどこかで 1 秒待つ必要がある。

#include <iostream>
using namespace std;

long long solve(long long sx, long long sy, long long gx, long long gy) {
    long long base = abs(sx - gx) + abs(sy - gy);
    if (sx == gx && sy == gy) return 0;
    else if (sx != gx && sy != gy) return base;
    else if (sx == gx) {
        if (sy % 2 == 0) {
            if (sy < gy) return base;
            else return base + 1;
        }
        else {
            if (sy > gy) return base;
            else return base + 1;
        }
    }
    else {
        if (sx % 2 == 0) {
            if (sx > gx || sx == gx - 1) return base;
            else return base + 1;
        }
        else {
            if (sx < gx || sx == gx + 1) return base;
            else return base + 1;
        }
    }
}

int main() {
    long long sx, sy, gx, gy;
    cin >> sx >> sy >> gx >> gy;
    cout << solve(sx, sy, gx, gy) << endl;
}