← 返回题目列表

AtCoder · joi2014yo_c

C. 超级大都会

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

配点: 100 点

問題

JOI君决定安排一次到IOI国超都这座城市的观光旅游。

超都南北方向直直延伸 W 本道路以及东西方向直直延伸的 H 由本道路划分为棋盘格的形状。

南北方向的 W 本道路,从西向东按顺序 1, 2, \ldots, W 编号。另外,东西方向的 H 这条路上,有 它的编号为 1, 2, \ldots, H 。从西边来 i 南北向南路 j 与东西路交叉口 由 (i, j) 代表。

此外,如下图所示,从每个路口到东北方向的一个路口都有一条路(不包括最北路路口和最东路路口)。还有一条通往西南一处路口的路(不包括最南路路口和最西路路口)。换句话说,交集 从 (i, j) 开始,如果交集 当有 (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1) 时,您可以使用一条道路到达这些路口。另外,如果有交叉路口 如果有 (i - 1, j - 1), (i + 1, j + 1) ,您可以使用一条路到达这些路口。

JOI 你已经在计划巡演了 我们正在决定参观 N 景点的顺序。i 番目 (1 \leqq i \leqq N) 中游览的旅游景点是路口 它位于 (X_i, Y_i) 。 JOI:您希望减少必须走的路数,以尽可能缩短游览时间。编写一个程序,找出按预定顺序访问旅游景点必须走的最少道路总数。

然而,游览的起点是在路口 (X_1, Y_1) 。此外,参加者在游览期间不得离开长岛。 JOI还可以通过旅游景点的路口而不去参观它们。

(初赛后添加) 有关“道路总数”的补充信息。游览时同一条路 您可以浏览 2 次以上。在这种情况下,“道路总数”将包括该道路行驶的次数。 由


入力

输入是 1 + N 行组成。 在

1 行上,使用空格作为分隔符。 3 整数 W, H, N (2 \leqq W \leqq 10\,000,2 \leqq H \leqq 10\,000,1 \leqq N \leqq 1\,000)被写入。

继续 表示第 N 行 i 行目 (1 \leqq i \leqq N)有 2 整数 X_i, Y_i (1 \leqq X_i \leqq W,1 \leqq Y_i \leqq H)以空格作为分隔符。这是 i 与您游览的旅游点的交叉路口是 (X_i, Y_i) 。

出力

依次访问旅游景点的道路总数的最小值为 输出为 1 行。


入力例 1

4 3 3
1 1
3 3
4 1

出力例 1

5

入出力例 1 例如, 您可以按以下顺序访问路口: (1, 1), (2, 2), (3, 3), (3, 2), (4, 2), (4, 1) 。 同一个路口可能会被访问​​多次,例如


入力例 2

4 3 5
1 3
4 3
2 2
2 2
1 3

出力例 2

7

入出力例 2 。