AT_nikkei2019_2_final_c Largest N

有一个 $H$ 行 $W$ 列的网格，每个格子被涂成黑色或白色。第 $i$ 行从上往下数，第 $j$ 列从左往右数，格子 $(i,\,j)$ 表示第 $i$ 行第 $j$ 列的格子。 格子 $(a_i,\,b_i)\ (1 \leq i \leq K)$ 被涂成白色，其余 $H \times W - K$ 个格子都被涂成黑色。 对于任意大于等于 $1$ 的整数 $k$，如果存在整数 $i,\,j$ 满足以下条件，则称网格中包含大小为 $k$ 的 “N”： - 所有格子 $(i + t,\,j)\ (0 \leq t < k)$ 都是黑色； - 所有格子 $(i + t,\,j + t)\ (0 \leq t < k)$ 都是黑色； - 所有格子 $(i + t,\,j + k - 1)\ (0 \leq t < k)$ 都是黑色； 并且，这些条件涉及到的所有格子都必须在 $H$ 行 $W$ 列的网格范围内。 请你求出网格中所包含的 “N” 的最大尺寸。如果不存在任何尺寸的 “N”，请输出 $0$。

输入通过标准输入给出，格式如下： > $H$ $W$ $K$ $a_1$ $b_1$ $a_2$ $b_2$ $\cdots$ $a_K$ $b_K$

请输出网格中所包含的 “N” 的最大尺寸。

### 限制条件 - $1 \leq H,\,W \leq 3000$ - $0 \leq K \leq \min(H \times W,\,2 \times 10^5)$ - $1 \leq a_i \leq H$ - $1 \leq b_i \leq W$ - $(a_i,\,b_i) \neq (a_j,\,b_j)\ (i \neq j)$ - 所有输入均为整数 ### 样例解释 1 网格如下所示（`#` 表示黑色，`.` 表示白色）： ``` ##.# #### ##.# ``` 此时，取 $i=1,\,j=2$，对于 $k=3$ 满足条件，因此该网格包含尺寸为 $3$ 的 “N”，且这是最大尺寸。 ### 样例解释 2 网格如下所示： ``` .. .. ``` 不包含任何尺寸的 “N”，因此输出 $0$。 ### 样例解释 3 网格如下所示： ``` .# #. ``` 取 $i=2,\,j=1$ 或 $i=1,\,j=2$，对于 $k=1$ 满足条件。 ### 样例解释 4 网格如下所示： ``` ##.# ##.# #.## #..# ``` 由 ChatGPT 4.1 翻译