984B. Minesweeper

B. Minesweeper

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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.

Alex 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?

He needs your help to check it.

A 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:

• if there is a digit $k$ in the cell, then exactly $k$ neighboring cells have bombs.
• if the cell is empty, then all neighboring cells have no bombs.

Two cells are neighbors if they have a common side or a corner (i. e. a cell has at most $8$neighboring cells).

Input

The first line contains two integers $n$ and $m$ ($1\le n,m\le 100$) — the sizes of the field.

The 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.

Output

Print "YES", if the field is valid and "NO" otherwise.

You can choose the case (lower or upper) for each letter arbitrarily.

Examples

input

Copy

3 3
111
1*1
111

output

Copy

YES

input

Copy

2 4
*.*.
1211

output

Copy

NO

Note

In 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.

You can read more about Minesweeper in Wikipedia's article.

题意： 一个人玩扫雷游戏，然你判断给的n*m的格子是否合法。如果n*m的格子要么空'.'要么是数字，表示周围的炸弹'*'。如果一个格子是炸弹，那么这个炸弹的上下左右（包括倾斜的）八个方向都应该加个数字1，表示周围存在一个炸弹。依次类推。最后然你判断给的格子是否合法。

题解： 我是建立了两个字符组，一个原来的输入的，一个现在开始扫雷的。如果有雷，就给雷周围八个方向加1，如果是点加编程点。最后判断两个字符组是否一样，一样就输出yes，否则就输出no。要注意细节，今天早上，上早自习的时候，发现没有过综测，结果掉分了。没过66组数据，因为我最开始的代码没有判断当前字符组是否是加过数字，遇到'.'就直接替换为'.'了,然后还要判断每个雷八个方向如果是雷就不要加1.否则输出的字符不是*了，变成其他对应ascll码的字符码了。

#include<bits/stdc++.h>
using namespace std;
char s[110][110],z[110][110];
int xx[8]= {1,-1,0,0,1,1,-1,-1},yy[8]= {0,0,-1,1,1,-1,1,-1},vis[110][110],n,m;
void dfs()
{
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
        {
          if(s[i][j]=='.'&&z[i][j]=='0')///昨晚综测没过66组，判断当前字符串是否是加过的，不然就不能换为点
              z[i][j]='.';
            if(s[i][j]=='*')
            {
                z[i][j]='*';
                for(int k=0; k<8; k++)
                {
                    int X=i+xx[k];
                    int Y=j+yy[k];
                    if(X>=0&&X<n&&Y>=0&&Y<m&&z[X][Y]!='*')///判断是否越界，每个炸弹周围是否有炸弹,不是炸弹的才能加1
                        z[X][Y]+=1;
                }
            }
        }
}
int main()
{
    cin>>n>>m;
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            cin>>s[i][j],z[i][j]='0';
    dfs();
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(s[i][j]!=z[i][j])
            {
                puts("NO");
                return 0;
            }
        }
    }
    puts("YES");
    return 0;
}