A - 高橋くんとマンハッタン 解説

実行時間制限: 2 sec / メモリ制限: 256 MB

問題文

高橋くんはマンハッタンにいます。マンハッタンは南北に伸びる道と東西に伸びる道で区画分けされており、どの道も十分長いため、南北に伸びる道と東西に伸びる道はどの組も交わり、その交わる点で交差点を作ります。また、南北に伸びる道同士、東西に伸びる道同士はそれぞれ交わりません。

西から xx 番目の南北に伸びる道と、南から yy 番目の東西に伸びる道の交わる交差点を (x,y)(x,y) と表すことにしましょう。

高橋くんは交差点 (x1,y1)(x_1,y_1) から交差点 (x2,y2)(x_2,y_2) へ行こうと考えています。このとき、最小でいくつの交差点を通らねばならないでしょうか?通る交差点には、交差点 (x1,y1)(x_1,y_1) と交差点 (x2,y2)(x_2,y_2) を含みます。

高橋くんが通らなければならない交差点の数を求めるプログラムを書いてください。


入力

入力は以下の形式で標準入力から与えられる。

x1x_1 y1y_1
x2x_2 y2y_2
  • 11 行目には、高橋くんが初めにいる交差点の場所を表す x1,y1(1x1,y1100,000)x_1, y_1 (1 ≦ x_1, y_1 ≦ 100,000) が与えられる。
  • 22 行目には、高橋くんの目的地の交差点の場所を表す x2,y2(1x2,y2100,000)x_2, y_2 (1 ≦ x_2, y_2 ≦ 100,000) が与えられる。
  • (x1,y1)(x2,y2)(x_1, y_1) ≠ (x_2, y_2) であることが保証される。つまり、目的地の交差点は初めにいる交差点とは異なる。

出力

11 行目に、高橋くんが初めにいる交差点から目的地の交差点へ行くときに通る最小の交差点の数を出力せよ。

行末の改行を忘れないこと。


入力例1Copy

Copy
3 3
2 5

出力例1Copy

Copy
4

S が初めにいる交差点、T が目的地の交差点です。

例えば、(3,3)(3,3) -> (2,3)(2,3) -> (2,4)(2,4) -> (2,5)(2,5) と進むと、44 つの交差点を通って目的地へ行くことができます。44 つ未満の交差点を通って行くことはできません。


入力例2Copy

Copy
1 2
1 1

出力例2Copy

Copy
2

(1,2)(1,2) -> (1,1)(1,1) と進むのが最適です。


入力例3Copy

Copy
20 40
32 64

出力例3Copy

Copy
37


2025-04-06 (日)
06:33:24 +00:00