← 返回题目列表

AtCoder · awc0083_d

D. 逃离溜冰场

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

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