← 返回题目列表

AtCoder · apc001_i

I. 简单的 APSP 问题

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

分数: 2000 点

问题陈述

您将获得 H \times W 网格。 左上角的正方形将表示为 (0, 0),右下角的方块将表示为 (H-1, W-1).

在这些方块中, N 方块 (x_1, y_1), (x_2, y_2), ..., (x_N, y_N) 被漆成黑色,其他方块被漆成白色。

设白色方块之间的最短距离 A 和 B 是达到目标所需的最少移动次数 B 来自 A 仅访问白色方块,可以一次移动到共享一侧(上、下、左或右)的相邻方格。

由于有 H × W - N 白色方块共有 _{(H×W-N)}C_2 选择两个白色方块的方法。

对于其中每一个 _{(H×W-N)}C_2 方法,找到所选方块之间的最短距离,然后找到所有这些距离的总和(模数) 1 000 000 007=10^9+7.

约束

  • 1 \leq H, W \leq 10^6
  • 1 \leq N \leq 30
  • 0 \leq x_i \leq H-1
  • 0 \leq y_i \leq W-1
  • If i \neq j,然后 x_i \neq x_j or y_i \neq y_j.
  • 至少有一个白色方块。
  • 对于每对白色方块 A 和 B,可以达到 B 来自 A 仅访问白色方块。

输入

输入由标准输入按以下格式给出:

H W
N
x_1 y_1
x_2 y_2
:
x_N y_N

输出

打印最短距离的总和,模数 10^9+7.


样本输入 1

2 3
1
1 1

示例输出 1

20

我们有以下网格(.:一个白色方块, #:黑色方块)。

...
.#.

让我们为每个白色方块分配一个字母,如下所示:

ABC
D#E

然后,我们有:

  • 距离(A,B)= 1
  • 距离(A,C)= 2
  • 距离(A,D)= 1
  • 距离(A,E)= 3
  • 距离(B,C)= 1
  • 距离(B,D)= 2
  • 距离(B,E)= 2
  • 距离(C,D)= 3
  • 距离(C,E)= 1
  • 距离(D,E)= 4

其中 dist(A, B) 是 A 和 B 之间的最短距离。这些距离的总和为 20.


示例输入 2

2 3
1
1 2

示例输出 2

16

让我们为每个白色方块分配一个字母,如下所示:

ABC
DE#

然后,我们有:

  • 距离(A,B)= 1
  • 距离(A,C)= 2
  • 距离(A,D)= 1
  • 距离(A,E)= 2
  • 距离(B,C)= 1
  • 距离(B,D)= 2
  • 距离(B,E)= 1
  • 距离(C,D)= 3
  • 距离(C,E)= 2
  • 距离(D,E)= 1

这些距离的总和是 16.


示例输入 3

3 3
1
1 1

示例输出 3

64

示例输入 4

4 4
4
0 1
1 1
2 1
2 2

示例输出 4

268

示例输入 5

1000000 1000000
1
0 0

示例输出 5

333211937