P15820 [JOI 2015 Final] 城墙 / Rampart
题目描述
身为历史学家的 JOI 教授，正在研究曾经存在的 IOI 王国。
根据过去的调查，IOI 王国是一个被划分为 $H$ 行 $W$ 列网格的长方形区域。IOI 王国的首都被用于防御的城墙所环绕。
环绕 IOI 王国首都的城墙具有以下形状。城墙定义了一个称为“大小”的值。大小为 $s$ ($s \ge 3$) 的城墙，是指从一个 $s \times s$ 的正方形区域中，挖去其内部一个 $(s-2) \times (s-2)$ 的正方形区域后剩下的边框部分。
调查表明，环绕首都的城墙大小至少为 $L$。此外，已知 IOI 王国的某些网格上**没有**城墙存在。
JOI 教授为了进一步研究，想知道可能的城墙有多少种。
### 任务
给定 IOI 王国的尺寸、城墙大小的最小值以及已知没有城墙存在的网格信息，请编写一个程序，计算可能的城墙有多少种。
输入格式
从标准输入读取以下数据。
* 第一行包含四个以空格分隔的整数 $H, W, L, P$。这表示 IOI 王国是一个 $H$ 行 $W$ 列的长方形区域，城墙大小至少为 $L$，并且已知有 $P$ 个网格上没有城墙存在。
* 接下来的 $P$ 行中，第 $i$ 行 ($1 \le i \le P$) 包含两个以空格分隔的整数 $A_i, B_i$。这表示已知 IOI 王国从上往下第 $A_i$ 行、从左往右第 $B_i$ 列的网格上没有城墙存在。
输出格式
向标准输出输出一行，包含一个整数，表示可能的城墙有多少种。
说明/提示
### 样例解释 1
在这个样例中，可能的城墙有以下 4 种。其中，用 × 标记的网格是已知没有城墙存在的网格。
:::align{center}
:::
### 数据范围
所有输入数据满足以下条件：
* $1 \le H \le 4000$。
* $1 \le W \le 4000$。
* $3 \le L \le H$ 且 $3 \le L \le W$。
* $0 \le P \le 100000$。
* $1 \le A_i \le H$ ($1 \le i \le P$)。
* $1 \le B_i \le W$ ($1 \le i \le P$)。
* $(A_i, B_i) \ne (A_j, B_j)$ ($1 \le i < j \le P$)。（即已知无城墙的网格位置互不相同）
### 子任务
#### 子任务 1 [4 分]
满足以下条件：
* $H \le 500$。
* $W \le 500$。
#### 子任务 2 [16 分]
* 满足 $0 \le P \le 10$。
#### 子任务 3 [80 分]
没有额外限制。
翻译由 DeepSeek V3.2 完成