/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 6 点
注意
この問題に対する言及は、2020/6/6 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
無限に広がる二次元グリッドがあります。 すぬけ君ははじめマス (0,0) にいます。 障害物のあるマスが N 個あり、すぬけ君は障害物のあるマスに移動することができません。i 番目の障害物はマス (x_i, y_i) にあります。 すぬけ君の現在位置をマス (x,y) としたとき、一回の移動で以下の 6 箇所のうちいずれかに移動できます。
- (x+1, y+1)
- (x, y+1)
- (x-1, y+1)
- (x+1, y)
- (x-1, y)
- (x, y-1)
最小で何回移動するとマス (X,Y) に到達できるか出力してください。到達することが不可能であれば -1 を出力してください。
制約
- 入力はすべて整数
- 1 \leq N \leq 800
- -200 \leq x_i, y_i, X, Y \leq 200
- (x_i, y_i) は相異なる。つまり、同じマスに 2 個以上の障害物はない。
- (0, 0) および (X, Y) には障害物はない
- (X, Y) \neq (0, 0)
入力
入力は以下の形式で標準入力から与えられる。
N X Y x_1 y_1 : x_N y_N
出力
問題で指定された整数を出力せよ。
入力例 1
1 2 2 1 1
出力例 1
3
以下にグリッドの一部を図示します。
..G .#. S..
ここで、S はマス (0, 0) を、G はマス (X, Y) = (2, 2) を、# は障害物のあるマスを表します。
最小で 3 回の移動で (X, Y) = (2, 2) に到達することができます。この回数は、例えば (0, 0) \to (0, 1) \to (1, 2) \to (2, 2) と移動すれば達成できます。
入力例 2
1 2 2 2 1
出力例 2
2
入力例 3
5 -2 3 1 1 -1 1 0 1 -2 1 -3 1
出力例 3
6
Score : 6 points
Warning
Do not make any mention of this problem until June 6, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
We have an infinite two-dimensional grid. Snuke is initially standing at the square (0,0) in this grid. There are N squares that contain an obstacle, and Snuke cannot enter those squares. The i-th obstacle is at the square (x_i, y_i). When Snuke is at the square (x, y), he can get to one of the following six squares in one move:
- (x+1, y+1)
- (x, y+1)
- (x-1, y+1)
- (x+1, y)
- (x-1, y)
- (x, y-1)
Print the minimum number of moves Snuke needs to reach the square (X, Y). If this square is unreachable, print -1.
Constraints
- All values in input are integers.
- 1 \leq N \leq 800
- -200 \leq x_i, y_i, X, Y \leq 200
- The pairs (x_i, y_i) are distinct. That is, no square contains two or more obstacles.
- The squares (0, 0) and (X, Y) do not contain an obstacle.
- (X, Y) \neq (0, 0)
Input
Input is given from Standard Input in the following format:
N X Y x_1 y_1 : x_N y_N
Output
Print an integer as specified in Problem Statement.
Sample Input 1
1 2 2 1 1
Sample Output 1
3
Shown below is a part of the grid:
..G .#. S..
Here, S, G, and # stand for the square (0, 0), (X, Y) = (2, 2), and a square with an obstacle.
The minimum number of moves needed to reach (X, Y) = (2, 2) is three. One way to achieve it is (0, 0) \to (0, 1) \to (1, 2) \to (2, 2).
Sample Input 2
1 2 2 2 1
Sample Output 2
2
Sample Input 3
5 -2 3 1 1 -1 1 0 1 -2 1 -3 1
Sample Output 3
6