分数: 525 点
问题陈述
有一个 H \times W 网格。让 (i,j) 表示位于 i从顶部开始的第行和 j左起第 列。其中, K 细胞是目标。这 i第一个目标 (1 \leq i \leq K) 是单元格 (R_i, C_i).
高桥和青木使用这个网格和放置在网格上的单个棋子玩游戏。高桥和青木重复执行以下一系列操作,直到棋子到达目标单元格:
- 青木选择一个整数 a 之间 1 和 4,包括在内。
- 然后,高桥选择一个整数 b 之间 1 和 4,包含在内,其中
必须满足 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);如果它在网格之外,则不执行任何操作。
高桥的目标是尽量减少棋子到达目标之前的移动次数。青木的目标是阻止棋子达到目标;如果这是不可能的,他的目标是最大化移动次数,直到棋子达到目标。
对于所有整数对 (i,j) 满意 1 \leq i \leq H,1 \leq j \leq W,解决以下问题并找到所有解决方案的总和:
从单元格中的棋子开始游戏 (i,j)。假设双方都以最佳方式实现各自的目标。如果高桥能让棋子达到目标,则解决方案是最少步数;否则,解决方案是 0.
约束
- 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)
- 所有输入值均为整数。
输入
输入由标准输入给出,格式如下:
H W K R_1 C_1 R_2 C_2 \vdots R_K C_K
输出
打印答案。
样本输入 1
2 3 2 1 2 2 1
示例输出 1
2
当 (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.
示例输入 2
9 3 9 1 3 6 1 4 1 1 2 2 1 7 1 9 3 8 1 9 2
示例输出 2
43
示例输入 3
10 10 36 3 8 5 10 3 10 6 10 2 10 2 8 7 10 1 10 1 8 7 6 7 8 2 5 1 6 8 8 7 5 2 4 9 8 7 4 4 3 10 10 10 8 8 10 10 6 6 2 4 2 10 5 8 3 1 2 2 1 4 1 10 4 10 3 8 1 6 1 10 2 9 1
示例输出 3
153