分数: 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