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