分数: 400 分
问题陈述
高桥被困在一个长方形溜冰场中, H 行和 W 列。有 N 冰场内立着柱子。的 i-th 柱子位于坐标处 (R_i, C_i)。这里,坐标 (r, c) 表示单元格中 r从顶部算起的第行和 c左起第 列。
高桥目前位于左上角的坐标 (1, 1) 目标是到达坐标右下角的目标 (H, W).
冰场上的冰面非常滑,一旦开始滑行,就无法改变方向或中途停止。在 一招,高桥选择四个方向之一——上、下、左或右——并开始滑动,继续沿该方向笔直滑动,直到满足以下条件之一:
- 到达溜冰场边缘: 由于他无法走出冰场,因此他停在边缘牢房处。
- 到达柱子前面的牢房: 如果滑动方向的下一个单元格包含柱子,则他无法进入有柱子的单元格,因此他会停在其前面的单元格处。
这里,向上表示行数减少的方向,向下表示行数增加,向左表示列数减少,向右表示列数增加。
如果他甚至无法在所选方向上前进一个单元格(即,相邻的单元格包含一根柱子,或者他已经位于溜冰场的边缘并且该方向上不存在单元格),则高桥不会移动并停留在当前的单元格中。 这仍然算作一步。
高桥可以多次访问同一个牢房。
求高桥从坐标出发所需的最少移动次数 (1, 1) 和 停止 位于坐标处 (H, W)。停在坐标处 (H, W) 表示,按照上述移动规则,他停在坐标处 (H, W)。简单地通过坐标 (H, W) 滑动时不算达到目标。
如果无法达到目标,则输出 -1.
保证坐标处没有柱子 (1, 1) 或坐标 (H, W).
约束
- 2 \leq H \leq 100
- 2 \leq W \leq 100
- 0 \leq N \leq H \times W - 2
- 1 \leq R_i \leq H
- 1 \leq C_i \leq W
- (R_i, C_i) \neq (1, 1)
- (R_i, C_i) \neq (H, W)
- If i \neq j,那么 (R_i, C_i) \neq (R_j, C_j)
- 所有输入值均为整数
输入
H W N R_1 C_1 R_2 C_2 \vdots R_N C_N
- 第一行包含 H,溜冰场的排数, W,列数,以及 N,柱子的数量,以空格分隔。
- 以下 N 行包含每个柱子的坐标。如果 N = 0,这部分不存在。
- 的 (1 + i)- 第行 (1 \leq i \leq N) 包含行号 R_i 和列号 C_i 的 i第一个支柱,以空格分隔。
输出
在一行中打印高桥停在坐标处所需的最少移动次数 (H, W) 从坐标开始 (1, 1)。如果不可能,则打印 -1.
示例输入 1
3 3 1 2 2
示例输出 1
2
示例输入 2
5 6 3 2 3 4 4 3 6
示例输出 2
2
示例输入 3
10 10 8 1 5 3 1 3 10 5 5 7 3 7 8 10 4 2 8
示例输出 3
4