F - No Passage Editorial /

Time Limit: 2.5 sec / Memory Limit: 1024 MiB

配点 : 525 点

問題文

H 行 W 列のグリッドがあります。上から i 行目、左から j 列目のマスを (i,j) と表します。また、このうち K 個のマスはゴールになっています。i 個目 (1 \leq i \leq K) のゴールはマス (R_i, C_i) です。

高橋君と青木君はこのグリッドとグリッドの上に置かれた 1 つのコマを使ってあるゲームをしています。高橋君と青木君はコマがゴールのマスに到達するまで以下の一連の操作を繰り返し行います。

  • 青木君は 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 が解である。

制約

  • 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

Score : 525 points

Problem Statement

There is an H \times W grid. Let (i,j) denote the cell at the i-th row from the top and j-th column from the left. Among these, K cells are goals. The i-th goal (1 \leq i \leq K) is cell (R_i, C_i).

Takahashi and Aoki play a game using this grid and a single piece placed on the grid. Takahashi and Aoki repeatedly perform the following series of operations until the piece reaches a goal cell:

  • Aoki chooses an integer a between 1 and 4, inclusive.
  • Then, Takahashi chooses an integer b between 1 and 4, inclusive, where a \neq b must be satisfied. Let (i,j) be the cell where the piece is placed before the operation. Based on the chosen integer b and the piece's position, move the piece.
    • When b=1: If (i-1,j) is within the grid, move the piece from cell (i,j) to cell (i-1,j); if it is outside the grid, do nothing.
    • When b=2: If (i+1,j) is within the grid, move the piece from cell (i,j) to cell (i+1,j); if it is outside the grid, do nothing.
    • When b=3: If (i,j-1) is within the grid, move the piece from cell (i,j) to cell (i,j-1); if it is outside the grid, do nothing.
    • When b=4: If (i,j+1) is within the grid, move the piece from cell (i,j) to cell (i,j+1); if it is outside the grid, do nothing.

Takahashi's objective is to minimize the number of moves until the piece reaches a goal. Aoki's objective is to prevent the piece from reaching the goal; if that is impossible, his objective is to maximize the number of moves until the piece reaches a goal.

For all pairs of integers (i,j) satisfying 1 \leq i \leq H,1 \leq j \leq W, solve the following problem and find the sum of all solutions:

Start the game with the piece at cell (i,j). Assume both players act optimally toward their respective objectives. If Takahashi can make the piece reach a goal, the solution is the minimum number of moves; otherwise, the solution is 0.

Constraints

  • 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)
  • All input values are integers.

Input

The input is given from standard input in the following format:

H W K
R_1 C_1
R_2 C_2
\vdots
R_K C_K

Output

Print the answer.

Sample Input 1

2 3 2
1 2
2 1

Sample Output 1

2

When (i,j)=(1,2),(2,1), the starting cell is a goal, so the solution is 0.

When (i,j)=(1,1),(2,2), no matter which a Aoki chooses, Takahashi can make the piece reach a goal in 1 move from the starting cell, so the solution is 1.

When (i,j)=(1,3),(2,3), Takahashi cannot reach a goal, so the solution is 0.

The sum of these is 0 \times 2 + 1 \times 2 + 0 \times 2 = 2. Thus, print 2.

Sample Input 2

9 3 9
1 3
6 1
4 1
1 2
2 1
7 1
9 3
8 1
9 2

Sample Output 2

43

Sample Input 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

Sample Output 3

153