AT_apc001_i Simple APSP Problem

给定一个 $H \times W$ 的网格。我们将左上角的格子记作 $(0,\ 0)$，右下角的格子记作 $(H-1,\ W-1)$。 在这些格子中，有 $N$ 个格子 $(x_1,\ y_1),\ (x_2,\ y_2),\ ...,\ (x_N,\ y_N)$ 被涂成黑色，其余格子为白色。 对白色格子 $A$ 与 $B$，定义它们之间的最短距离为：仅通过**白色格子**从 $A$ 走到 $B$ 所需要移动的最小步数。每一步只能移动到上下左右相邻的格子。 由于白色格子共有 $H \times W - N$ 个，所以可以从中任选两个格子的方案数为 $_{(H\times W-N)}C_2$。 请对于所有 $_{(H\times W-N)}C_2$ 种选取的方式，分别求出选中两格之间的最短距离，将所有距离加和并对 $1,\!000,\!000,\!007 = 10^9 + 7$ 取余。

输入通过标准输入依下述格式给出。 > $H$ $W$ $N$ $x_1$ $y_1$ $x_2$ $y_2$ $:$ $x_N$ $y_N$

输出最短距离总和对 $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$ - 当 $i \neq j$ 时，$x_i \neq x_j$ 或 $y_i \neq y_j$ - 至少存在一个白色格子 - 任意两个白色格子 $A, B$ 之间，仅通过白色格子可互相到达 ## 样例说明 1 该网格的色彩分布如下（`.` ：白色，`#` ：黑色）： ``` ... .#. ``` 此时，给白格编号如下所示： ``` ABC D#E ``` 则有： - dist(A, B) = $1$ - dist(A, C) = $2$ - dist(A, D) = $1$ - dist(A, E) = $3$ - dist(B, C) = $1$ - dist(B, D) = $2$ - dist(B, E) = $2$ - dist(C, D) = $3$ - dist(C, E) = $1$ - dist(D, E) = $4$ 这些距离的总和为 $20$。其中，dist(A, B) 表示格子 A 和 B 之间的最短距离。 ## 样例说明 2 给白格编号如下： ``` ABC DE# ``` 则有： - dist(A, B) = $1$ - dist(A, C) = $2$ - dist(A, D) = $1$ - dist(A, E) = $2$ - dist(B, C) = $1$ - dist(B, D) = $2$ - dist(B, E) = $1$ - dist(C, D) = $3$ - dist(C, E) = $2$ - dist(D, E) = $1$ 这些距离的总和为 $16$。 由 ChatGPT 5 翻译