P16585 [GKS 2016 #C] Safe Squares

Codejammon 的训练师们正在积极寻找怪物，但如果你不是训练师，这些怪物对你来说可能非常危险。你可能想找到完全没有怪物的安全地点！ 将我们的世界视为一个网格，其中某些格子已被怪物占据。我们定义一个**安全正方形**为一个与网格对齐的 $D \times D$ 的正方形（$D \ge 1$），且该正方形内不包含任何怪物。你的任务是计算在整个世界中有多少个（任意大小的）安全正方形。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含三个整数 $R$、$C$ 和 $K$。网格有 $R$ 行 $C$ 列，包含 $K$ 个怪物。接下来 $K$ 行，每行包含两个整数 $R_i$ 和 $C_i$，表示第 $i$ 个怪物所在的行和列。（行从上到下编号，从 $0$ 开始；列从左到右编号，从 $0$ 开始。）

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是该测试用例中安全正方形的总数。

样例 #1 的网格为： ``` 0 0 0 0 0 0 0 1 0 ``` 这里，0 表示没有怪物的格子，1 表示有怪物的格子。共有 $10$ 个安全正方形：$8$ 个 $1\times 1$ 和 $2$ 个 $2\times 2$。 样例 #2 的网格为： ``` 0 1 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 ``` 请注意，样例 #2 只会出现在大数据集中。它有 $51$ 个安全正方形：$32$ 个 $1\times 1$，$13$ 个 $2\times 2$，$5$ 个 $3\times 3$，以及 $1$ 个 $4\times 4$。 ### 限制条件 $1 \le T \le 20$。 对于 $i \ne j$，有 $(R_i, C_i) \ne (R_j, C_j)$。（没有两个怪物在同一个格子内。） $0 \le R_i < R$，$i = 1 \dots K$。 $0 \le C_i < C$，$i = 1 \dots K$。 **小数据集（测试集 1 – 可见）** $1 \le R \le 10$。 $1 \le C \le 10$。 $0 \le K \le 10$。 **大数据集（测试集 2 – 隐藏）** $1 \le R \le 3000$。 $1 \le C \le 3000$。 $0 \le K \le 3000$。 翻译由 DeepSeek V4 Pro 完成