AT_abc413_f.[ABC413F] No Passage

有一个 $H$ 行 $W$ 列的网格。我们用 $(i,j)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子。在这些格子中，有 $K$ 个格子是“终点”。第 $i$ 个终点（$1 \leq i \leq K$）位于格子 $(R_i, C_i)$。

高桥君和青木君用这个网格和放在网格上的一个棋子进行游戏。棋子到达终点格子之前，两人会不断重复以下操作：

• 青木君选择一个 $1$ 到 $4$ 之间的整数 $a$。
• 然后，高桥君选择一个 $1$ 到 $4$ 之间的整数 $b$，但要求 $a \neq b$。假设操作前棋子在 $(i,j)$，则根据 $b$ 的值和棋子的位置，按如下方式移动棋子：
  • 若 $b=1$：如果 $(i-1,j)$ 在网格内，则将棋子从 $(i,j)$ 移动到 $(i-1,j)$，否则不移动。
  • 若 $b=2$：如果 $(i+1,j)$ 在网格内，则将棋子从 $(i,j)$ 移动到 $(i+1,j)$，否则不移动。
  • 若 $b=3$：如果 $(i,j-1)$ 在网格内，则将棋子从 $(i,j)$ 移动到 $(i,j-1)$，否则不移动。
  • 若 $b=4$：如果 $(i,j+1)$ 在网格内，则将棋子从 $(i,j)$ 移动到 $(i,j+1)$，否则不移动。

高桥君的目标是让棋子以最少的步数到达终点。青木君的目标是让棋子无法到达终点，如果无法做到，则尽量让步数最大化。

对于所有满足 $1 \leq i \leq H, 1 \leq j \leq W$ 的整数对 $(i,j)$，请解决以下问题，并求出所有解的总和：

棋子从格子 $(i,j)$ 开始游戏。两人都以各自的目标采取最优策略。如果高桥君能让棋子到达终点，则输出所需的最小步数，否则输出 $0$。

输入按以下格式从标准输入读入：

$H$ $W$ $K$
$R_1$ $C_1$
$R_2$ $C_2$
$\vdots$
$R_K$ $C_K$

请输出答案。

限制条件

• $2 \leq H \leq 3000$
• $2 \leq W \leq 3000$
• $1 \leq K \leq \min(HW, 3000)$
• $1 \leq R_i \leq H$
• $1 \leq C_i \leq W$
• $(R_i, C_i) \neq (R_j, C_j)$（$1 \leq i < j \leq K$）
• 所有输入均为整数

样例解释 1

当 $(i,j)=(1,2),(2,1)$ 时，起始格子就是终点，因此答案为 $0$。当 $(i,j)=(1,1),(2,2)$ 时，无论青木君选择哪个 $a$，高桥君都能用 $1$ 步将棋子移动到终点，因此答案为 $1$。当 $(i,j)=(1,3),(2,3)$ 时，高桥君无法让棋子到达终点，因此答案为 $0$。这些的总和为 $0 \times 2 + 1 \times 2 + 0 \times 2 = 2$。因此输出 $2$。

由 ChatGPT 4.1 翻译