← 返回题目列表

Codeforces · 984/B

B. 扫雷

中文机器翻译题面 查看原题

有一天,亚历克斯决定回忆童年,当时电脑的功能还不是太强大,很多人只玩默认游戏。那次亚历克斯很喜欢玩扫雷。他想象自己能从恐怖分子安放的炸弹中拯救世界,但他很少获胜。

Alex从那时起就长大了,所以他轻松地赢得了最困难的关卡。这很快让他感到厌烦,他想:如果计算机在童年时给了他无效的字段,而亚历克斯因此无法获胜怎么办?

他需要你的帮助来检查。

扫雷字段是一个矩形 $$$n \times m$$$,其中每个单元格要么为空,要么包含从 $$$1$$$ 到 $$$8$$$ 的数字,或者炸弹。如果对于每个单元格,该字段有效:

- 如果单元格中有数字 $$$k$$$,则恰好 $$$k$$$ 相邻单元格有炸弹。
- 如果该单元格为空,则所有相邻单元格都没有炸弹。

如果两个单元格具有共同的边或角(即一个单元格最多有 $$$8$$$ 个相邻单元格),则它们是邻居。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 100$$$) — 字段的大小。

接下来的 $$$n$$$ 行包含字段的描述。每行包含 $$$m$$$ 个字符,每个字符都是“.”。 (如果此单元格为空)、“*”(如果此单元格中有炸弹)或 $$$1$$$ 到 $$$8$$$(含)之间的数字。

输出

如果该字段有效,则打印“是”,否则打印“否”。

您可以任意选择每个字母的大小写(小写或大写)。

示例

输入 #1

3 3
111
1*1
111

输出 #1

YES

输入 #2

2 4
*.*.
1211

输出 #2

NO

注意

在第二个示例中,答案是“否”,因为如果保留炸弹的位置,则该字段的第一行应该是 *2*1。

您可以在维基百科的文章中阅读有关扫雷的更多信息。