Codeforces Round #483 (Div. 2) B. 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×mn×m, where each cell is either empty, or contains a digit from 11 to 88, or a bomb. The field is valid if for each cell:

  • if there is a digit kk in the cell, then exactly kk 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 88 neighboring cells).

Input

The first line contains two integers nn and mm (1≤n,m≤1001≤n,m≤100) — the sizes of the field.

The next nn lines contain the description of the field. Each line contains mm characters, each of them is "." (if this cell is empty), "*" (if there is bomb in this cell), or a digit from 11 to 88, 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的矩阵,问是否合理。其中*表示炸弹,‘.’表示这一点附近八个方向都没有炸弹,其他数字表示这一点附近八个方向炸弹个数。

也就是给你的矩阵,‘*’是已知,判断别的点对不对。

我们处理字符矩阵,把是'*'的附近八个方向都加加放在另外一个数组中,最后对比原来的数组就可以。

#include <iostream> #include <algorithm> #include <cstring> using namespace std; int mp[105][105]; int ans[105][105]; int n,m; int dir[][2]={-1,1, 0,1, 1,1, -1,0, 1,0, -1,-1, 0,-1, 1,-1}; int main() { while(~scanf("%d %d",&n,&m)) {       memset(mp,-1,sizeof(mp));    memset(ans,0,sizeof(ans));    char tp; getchar();  for(int i=1;i<=n;i++)   for(int j=1;j<=m;j++)   {    scanf("%c",&tp);  if(tp=='*')  {mp[i][j]=-2;//-2表示有炸弹     for(int k=0;k<8;k++)      { int tx,ty; tx=dir[k][0]+i; ty=dir[k][1]+j; if(i>=1&&i<=n&&j>=1&&j<=m&&mp[i][j]!=-1) ans[tx][ty]++;   }       }  else if(tp=='.')         mp[i][j]=0,ans[i][j]=0;//-1表示空           else  mp[i][j]=tp-'0';  if(j==m)getchar();   }   int flag=1;     for(int i=1;i<=n;i++)         for(int j=1;j<=m;j++)            { if(mp[i][j]!=-1&&mp[i][j]!=-2&&mp[i][j]!=ans[i][j])   {//printf("%d %d %d %d",ans[i][j],mp[i][j],i,j);   flag=0;   break;      } }  if(flag) printf("YES\n"); else printf("NO\n"); }     return 0; } 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏云时之间

python学习之文章数据分析

通常我们在进行NLP学习的时候,会经常的处理一些语料,同时也会对这些语料进行一些分析,今天的这篇文章我们通过分析quora上的Andrew NG的一个回答来实际...

3616
来自专栏ml

mxnet框架样本,使用C++接口

哇塞,好久么有跟进mxnet啦,python改版了好多好多啊,突然发现C++用起来才是最爽的. 贴一个mxnet中的C++Example中的mlp网络和实现,感...

9915
来自专栏潇涧技术专栏

Python Algorithms - C7 Greedy

Python算法设计篇(7) Chapter 7: Greed is good? Prove it!

1132
来自专栏数据结构与算法

BZOJ4128: Matrix(BSGS 矩阵乘法)

第一行两个整数n和p,表示矩阵的阶和模数,接下来一个n * n的矩阵A.接下来一个n * n的矩阵B

712
来自专栏数据结构与算法

HDU 3078 Network

Problem Description The ALPC company is now working on his own network system,...

3497
来自专栏小樱的经验随笔

HDU 2080 夹角有多大II

夹角有多大II Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (J...

27510
来自专栏计算机视觉与深度学习基础

Leetcode 200 Number of Islands 并查集

Given a 2d grid map of '1's (land) and '0's (water), count the number of islan...

2457
来自专栏数据结构与算法

2017.9.17校内noip模拟赛解题报告

预计分数:100+60+60=220 实际分数:100+60+40=200 除了暴力什么都不会的我。。。。。 T1 2017.9.17巧克力棒(chocolat...

4157
来自专栏量化投资与机器学习

【代码+论文】通过ML、Time Series模型学习股价行为

今天编辑部给大家带来的是来自Jeremy Jordan的论文,主要分析论文的建模步骤和方法,具体内容大家可以自行查看。 # Standard imports i...

4698
来自专栏HansBug's Lab

4063: [Cerc2012]Darts

4063: [Cerc2012]Darts Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 85  Solve...

35411

扫码关注云+社区

领取腾讯云代金券