← 返回题目列表

AtCoder · nikkei2019_final_c

C. 一起来

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

配点 : 300 点

問題文

縦 H 行、横 W 有一个列网格。 从上面 i 行,从左 j 标记列中的方块 (i,j) 。 所有满足

在每个方格中,1 放置了两块。 肖先生就是其中之一 K 碎片已从正方形顶部移除。 第 i 个被移除的块是 这是 (R_i,C_i) 中的作品。

Shaw 先生现在将执行以下操作。 执行此操作至少 0 次。

  • 件 1 选择一个并将其从当前放置的方格移动到另一个相邻的方格。 此时,目标方格内是否还有棋子也没关系。 此外,2 两个正方形彼此相邻。2 表示两个正方形共享一条边。

Sho先生的目标是确保一个方格上的所有棋子都放在同一个方格上。 求寿先生实现目标所需的最少操作次数。

制約

  • 1 \leq H \leq 10^5
  • 1 \leq W \leq 10^5
  • 0 \leq K \leq \min(10^5,H \times W -1)
  • 1\leq R_i \leq H
  • 1\leq C_i \leq W
  • (R_i,C_i) \neq (R_j,C_j) (i\neq j)
  • 所有输入值都是整数。 如果您想走

入力

输入是按以下格式从标准输入给出的。

H W K
R_1 C_1
R_2 C_2
\vdots
R_K C_K

出力

输出使方格上的所有棋子放在同一个方格上所需的最少操作次数。


入力例 1

2 3 3
1 2
2 1
2 2

出力例 1

3

操作前放置棋子的方格是 (1,1), (1,3), (2,3) 可以得到第 3 一。 如下 通过操作 3 次,所有棋子将被放置在同一个方块上。

  • 质量 从 (1,1) 上的棋子摆成正方形 移至 (1,2) 。
  • 质量 从 (1,2) 上的棋子摆成正方形 移至 (1,3) 。
  • 质量 从 (2,3) 上的棋子摆成正方形 移至 (1,3) 。

2 由于较少的操作无法达到目的,3 就是答案。


入力例 2

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

出力例 2

28

入力例 3

100000 100000 0

出力例 3

500000000000000

入力例 4

2 2 3
1 2
2 1
2 2

出力例 4

0