← 返回题目列表

AtCoder · past202005_g

G. 金将军上线

中文机器翻译题面 查看原题

分数: 6 点

警告

2020 年 6 月 6 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。

问题陈述

我们有一个无限的二维网格。 Snuke最初站在广场上 (0,0) 在此网格中。 有 N 包含障碍物的方格,Snuke 无法进入这些方格。的 i第一个障碍物在广场上 (x_i, y_i)。 当斯努克在广场上时 (x, y),他可以一步到达以下六个方格之一:

  • (x+1, y+1)
  • (x, y+1)
  • (x-1, y+1)
  • (x+1, y)
  • (x-1, y)
  • (x, y-1)

打印 Snuke 到达方块所需的最小移动次数 (X, Y)。如果该方块无法到达,则打印 -1.

约束

  • 输入中的所有值都是整数。
  • 1 \leq N \leq 800
  • -200 \leq x_i, y_i, X, Y \leq 200
  • 对 (x_i, y_i) 是不同的。也就是说,没有一个正方形包含两个或多个障碍物。
  • 方块 (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, G,和 # 代表正方形 (0, 0), (X, Y) = (2, 2),以及一个有障碍物的正方形。

达到目标所需的最少移动次数 (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