← 返回题目列表

AtCoder · joi2013ho3

3. 现代大厦

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

配点: 100 点

你走进了一座大宅邸。这座宅邸的房间呈方形,呈南北、东西方格子状排列。 M 柱,南北方向 N 行总计 它具有 M \times N 块排列的结构。从西边来 x 列目 (1 \leqq x \leqq M),从南边 y 行目 (1 \leqq y \leqq N) 由 (x, y) 代表。

毗邻北、南、东、西 2 房间由墙中央的门连接。每扇门要么关闭且无法通行,要么打开且可通行。当门打开时在房间的中心之间移动。 需要 1 分钟。另外,部分房间中央设有开关; 1 如果按住它一分钟,宅邸中的所有门都会在打开和关闭状态之间切换。

现在东西相邻 2 连接房间的门全部关闭,南北相邻。 2 连接房间的所有门都打开。你现在在房间里 (1, 1) 在房间中央 我想在最短的时间内移动到 (M, N) 的中心。

課題

豪宅的大小 M, N 并带有开关 K 房间位置 给出 (X_1, Y_1), (X_2, Y_2), \ldots, (X_K, Y_K) 。东边和西边毗邻 2 连接房间的门全部关闭,南北相邻。 2 首先打开所有连接房间的门,并且 (1, 1) 从房间的中心 编写一个程序,求移动到 (M, N) 中心所需的最少分钟数。不过,房间 如果您无法到达 (M, N) ,请指出。

制限

2 \leqq M \leqq 100\,000  豪宅东西方向房间数
2 \leqq N \leqq 100\,000  宅邸南北方向房间数
1 \leqq K \leqq 200\,000  有开关的房间数量
1 \leqq X_i \leqq M  有开关房间的东西位置
1 \leqq Y_i \leqq N  有开关房间的南北位置

入力

从标准输入读取以下数据。

  • 1 行包含一个整数 M, N, K 以空格作为分隔符。M 是豪宅东西方向的房间数,N 是豪宅南北方向的房间数,K 代表有开关的房间数量。
  • 继续 K 行 i 行目 (1 \leqq i \leqq K) 是一个整数 X_i, Y_i 以空格作为分隔符。这是房间 (X_i, Y_i) 表示中央有一个开关。K 一套 (X_1, Y_1), (X_2, Y_2), \ldots, (X_K, Y_K) 彼此不同。

出力

指示移动所需的最小分钟数的整数被发送到标准输出。 输出为 1 行。不过,房间 如果无法达到 (M, N) ,则改为整数 输出 -1 。

採点基準

评分数据中,分配的分数 20 对于%,M \leqq 1\,000,N \leqq 1\,000 很满意。

评分数据中,分配的分数 30 对于%,K \leqq 2\,000 很满意。

评分数据中,分配的分数 50 对于 %,这些 2 至少满足以下条件之一。还有,这些 2 没有满足这两个条件的评分数据。


入力例 1

3 2 1
1 2

出力例 1

4

在此示例中,执行以下操作 4 几分钟内即可到达房间 您可以移动到 (1, 1) 从房间的中心 编写一个程序,求移动到 (3, 2) 的中心,这是最短的。 移至

  • 部屋 (1, 2) 的中心。 按下
  • 部屋 (1, 2) 中心的开关。
  • 部屋 (2, 2) 的中心。 按下
  • 部屋 (3, 2) 的中心。 按下

此时豪宅的状态如下图所示。图中,右侧方向为东,上方方向为北,x 标记代表您的位置,○ 标记代表开关。


入力例 2

3 2 1
2 1

出力例 2

-1

在此示例中,您在房间中 无法到达 (3, 2) 。


入力例 3

8 9 15
3 1
3 2
3 7
3 8
1 1
4 5
4 3
5 6
5 8
6 3
6 2
7 5
8 9
8 6
8 5

出力例 3

25

在这个例子中,第一座豪宅如下图所示。房间 (1, 1) 和房间 (M, N) 中间可能有一个开关。