← 返回题目列表

AtCoder · abc413_f

I. 没有通过

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

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