{"problem":{"name":"B. Minesweeper","description":{"content":"One day Alex decided to remember childhood when computers were not too powerful and lots of people played only default games. Alex enjoyed playing Minesweeper that time. He imagined that he saved worl","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF984B"},"statements":[{"statement_type":"Markdown","content":"One day Alex decided to remember childhood when computers were not too powerful and lots of people played only default games. Alex enjoyed playing Minesweeper that time. He imagined that he saved world from bombs planted by terrorists, but he rarely won.\n\nAlex has grown up since then, so he easily wins the most difficult levels. This quickly bored him, and he thought: what if the computer gave him invalid fields in the childhood and Alex could not win because of it?\n\nHe needs your help to check it.\n\nA Minesweeper field is a rectangle $n \\times m$, where each cell is either empty, or contains a digit from $1$ to $8$, or a bomb. The field is valid if for each cell:\n\n*   if there is a digit $k$ in the cell, then exactly $k$ neighboring cells have bombs.\n*   if the cell is empty, then all neighboring cells have no bombs.\n\nTwo cells are neighbors if they have a common side or a corner (i. e. a cell has at most $8$ neighboring cells).\n\n## Input\n\nThe first line contains two integers $n$ and $m$ ($1 \\le n, m \\le 100$) — the sizes of the field.\n\nThe next $n$ lines contain the description of the field. Each line contains $m$ characters, each of them is \"_._\" (if this cell is empty), \"_*_\" (if there is bomb in this cell), or a digit from $1$ to $8$, inclusive.\n\n## Output\n\nPrint \"_YES_\", if the field is valid and \"_NO_\" otherwise.\n\nYou can choose the case (lower or upper) for each letter arbitrarily.\n\n[samples]\n\n## Note\n\nIn the second example the answer is \"_NO_\" because, if the positions of the bombs are preserved, the first line of the field should be _*2*1_.\n\nYou can read more about Minesweeper in [Wikipedia's article](https://en.wikipedia.org/wiki/Minesweeper_(video_game)).","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"有一天，Alex 回忆起童年时代，那时计算机还不够强大，很多人只玩默认游戏。Alex 当时很喜欢玩扫雷。他想象自己拯救了世界，免受恐怖分子埋设的炸弹威胁，但他很少赢过。\n\n自从那时起，Alex 长大了，他能轻松赢得最困难的关卡。这很快让他感到无聊，于是他想：如果当年电脑给他的是无效的棋盘，而他因为这个原因无法获胜呢？\n\n他需要你的帮助来验证这一点。\n\n扫雷棋盘是一个 $n \\times m$ 的矩形，每个格子要么为空，要么包含一个从 $1$ 到 $8$ 的数字，要么是一个炸弹。一个棋盘是有效的，当且仅当对于每个格子：\n\n两个格子是邻居，当且仅当它们有一条公共边或一个公共角（即一个格子最多有 $8$ 个邻居）。\n\n第一行包含两个整数 $n$ 和 $m$ ($1 lt.eq n, m lt.eq 100$) —— 棋盘的尺寸。\n\n接下来的 $n$ 行包含棋盘的描述。每行包含 $m$ 个字符，每个字符是 \"_._\"（表示该格子为空）、\"_*_\"（表示该格子有炸弹），或一个从 $1$ 到 $8$ 的数字。\n\n如果棋盘有效，请输出 \"_YES_\"，否则输出 \"_NO_\"。\n\n你可以任意选择每个字母的大小写。\n\n在第二个示例中，答案是 \"_NO_\"，因为如果炸弹的位置保持不变，棋盘的第一行应该是 _*2*1_。\n\n你可以在维基百科的文章中阅读更多关于扫雷的信息。\n\n## Input\n\n第一行包含两个整数 $n$ 和 $m$ ($1 lt.eq n, m lt.eq 100$) —— 棋盘的尺寸。接下来的 $n$ 行包含棋盘的描述。每行包含 $m$ 个字符，每个字符是 \"_._\"（表示该格子为空）、\"_*_\"（表示该格子有炸弹），或一个从 $1$ 到 $8$ 的数字。\n\n## Output\n\n如果棋盘有效，请输出 \"_YES_\"，否则输出 \"_NO_\"。你可以任意选择每个字母的大小写。\n\n[samples]\n\n## Note\n\n在第二个示例中，答案是 \"_NO_\"，因为如果炸弹的位置保持不变，棋盘的第一行应该是 _*2*1_。你可以在维基百科的文章中阅读更多关于扫雷的信息。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z} $ be the dimensions of the grid, with $ 1 \\leq n, m \\leq 100 $.  \nLet $ G = (g_{i,j})_{i=1,\\dots,n;\\, j=1,\\dots,m} $ be a grid where each cell $ g_{i,j} \\in \\{ \\text{`.`}, \\text{`*`}, \\text{`1`}, \\text{`2`}, \\dots, \\text{`8`} \\} $.\n\nLet $ B \\subseteq \\{1,\\dots,n\\} \\times \\{1,\\dots,m\\} $ be the set of bomb positions:  \n$ B = \\{ (i,j) \\mid g_{i,j} = \\text{`*`} \\} $.\n\nFor each cell $ (i,j) \\notin B $, define $ N(i,j) $ as the set of its 8 neighbors:  \n$ N(i,j) = \\{ (i',j') \\mid |i - i'| \\leq 1, |j - j'| \\leq 1, (i',j') \\neq (i,j) \\} \\cap (\\{1,\\dots,n\\} \\times \\{1,\\dots,m\\}) $.\n\nLet $ c(i,j) = |N(i,j) \\cap B| $ be the number of bombs adjacent to cell $ (i,j) $.\n\n**Constraints**  \nFor all $ (i,j) \\in \\{1,\\dots,n\\} \\times \\{1,\\dots,m\\} $:  \n- If $ g_{i,j} = \\text{`*`} $, then no constraint on neighbors.  \n- If $ g_{i,j} \\in \\{ \\text{`1`}, \\text{`2`}, \\dots, \\text{`8`} \\} $, then $ g_{i,j} = c(i,j) $ must hold.  \n- If $ g_{i,j} = \\text{`.`} $, then $ c(i,j) = 0 $ must hold.\n\n**Objective**  \nDetermine whether the grid $ G $ satisfies:  \n$$\n\\forall (i,j), \\quad\ng_{i,j} =\n\\begin{cases}\n\\text{`*`} & \\text{if } (i,j) \\in B \\\\\n\\text{`.`} & \\text{if } (i,j) \\notin B \\text{ and } c(i,j) = 0 \\\\\n\\text{`d`} & \\text{if } (i,j) \\notin B \\text{ and } c(i,j) = d \\in \\{1,2,\\dots,8\\}\n\\end{cases}\n$$\n\nOutput \"YES\" if valid, \"NO\" otherwise.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF984B","tags":["implementation"],"sample_group":[["3 3\n111\n1*1\n111","YES"],["2 4\n*.*.\n1211","NO"]],"created_at":"2026-03-03 11:00:39"}}