扫雷

题目描述

小杨同学正在游玩经典游戏「扫雷」，他想自己生成一个「扫雷」的地图。

小杨同学希望生成的地图大小为 $n$ 行 $m$ 列，一共 $n \times m$ 个区块。区块行号为 $1, 2, \cdots, n$，列号为 $1, 2, \cdots, m$。其中一些区块为雷区，其它区块不为雷区。

小杨同学指定了 $q$ 个区块为雷区，而其它区块均不为雷区。小杨同学希望你帮忙计算非雷区的区块，每个区块与多少个雷区相邻？

我们定义区块相邻，当且仅当两个区块至少有一个公共顶点（也就是说对于不在地图边缘的区块，周围 $8$ 个区块均与其相邻）。

输入格式

输入包含 $q + 1$ 行。

第一行，三个正整数 $n$, $m$ 和 $q$，分别表示地图行数和列数，以及雷区数量。

接下来的 $q$ 行，每行有 $2$ 个整数，分别表示第 $i$ 个雷区的行号和列号。

保证输入的雷区不重复。

输出格式

输出 $n$ 行，每行 $m$ 个字符（使用空格分隔），对于第 $i$ 行第 $j$ 列，输出地图对应区块的信息：

1. 如果为雷区，输出 *；
2. 如果不是雷区，输出其相邻雷区数量（输出 $0$ 到 $8$ 中的一个数字）。

样例输入

3 4 4
1 1
1 3
2 4
3 2

样例输出

* 2 * 2
2 3 3 *
1 * 2 1

样例解释

根据输入，地图为 $3$ 行 $4$ 列，有 $4$ 个雷区，坐标分别为 $(1,1)$、$(1,3)$、$(2,4)$ 和 $(3,2)$。输出中 * 表示雷区，其余数字表示该非雷区与多少个雷区相邻。例如，第 $2$ 行第 $2$ 列的区块（非雷区）与三个雷区相邻：$(1,1)$、$(1,3)$ 和 $(3,2)$，因此输出 $3$；第 $1$ 行第 $2$ 列的区块与两个雷区 $(1,1)$ 和 $(1,3)$ 相邻，输出 $2$。其余位置同理，最终输出如样例所示。

数据范围

• $3 \le n, m \le 500$
• $1 \le q \le n \cdot m$
• 输入的雷区均在地图内且不重复，行号和列号从 $1$ 开始。