time limit per test 2 seconds
memory limit per test 256 megabytes
input standardinput
output standard output
Student Andrey has been skipping physical education lessons for the whole term, and now he must somehow get a passing grade on this subject. Obviously, it is impossible to do this by legal means, but Andrey doesn’t give up. Having obtained an empty certificate from a local hospital, he is going to use his knowledge of local doctor’s handwriting to make a counterfeit certificate of illness. However, after writing most of the certificate, Andrey suddenly discovered that doctor’s signature is impossible to forge. Or is it?For simplicity, the signature is represented as an n×mn×m grid, where every cell is either filled with ink or empty. Andrey’s pen can fill a 3×33×3square without its central cell if it is completely contained inside the grid, as shown below.
xxx
x.x
xxx
Determine whether is it possible to forge the signature on an empty n×mn×m grid.
Input
The first line of input contains two integers nn and mm (3≤n,m≤10003≤n,m≤1000).Then nn lines follow, each contains mm characters. Each of the characters is either ‘.’, representing an empty cell, or ‘#’, representing an ink filled cell.
Output
If Andrey can forge the signature, output “YES”. Otherwise output “NO”.You can print each letter in any case (upper or lower).
Examples
inputCopy3 3
#.#
outputCopy
YES
inputCopy3 3
outputCopy
NO
inputCopy4 3
outputCopy
YES
inputCopy5 7
…
.#####.
.#.#.#.
.#####.
…
outputCopy
YES
NoteIn the first sample Andrey can paint the border of the square with the center in (2,2)(2,2).In the second sample the signature is impossible to forge.In the third sample Andrey can paint the borders of the squares with the centers in (2,2)(2,2) and (3,2)(3,2):we have a clear paper:
…
…
…
…
use the pen with center at (2,2)(2,2).
#.#
…
use the pen with center at (3,2)(3,2).
In the fourth sample Andrey can paint the borders of the squares with the centers in (3,3)(3,3) and (3,5)(3,5).
理解：
对于这道题目 其实在拿到的时候是有点懵逼的 后来看了学长的代码才有了头绪 其实这道题说是思维 更像是枚举 首先最重要的是我们把每一个九宫格的左上角的那一个点来代表这个九宫格 然后去找可以当做下笔点的每一个九宫格 这个过程的实现思路就是设置一个vis二维数组 专门来记录这个点是否已经被遍历过 如果没有被遍历过 则把以这个点为左上角的vis数组里的值全部标记为以以遍历 如果遍历过 则去看以这个点为左上角的九宫格是否全部为 ‘#’ 如果是说明这个九宫格也可以下笔 然后全部遍历 有两种情况情况可以说这个图案不能实现
- 横竖坐标为最后两行 但 ‘#’ 仍为未标记 我们的笔不可以标到纸外 所以这样不可以
- 九宫格左上角未标记 但其中有非 ‘#’ 的字符
以下是AC代码：
#include<stdio.h>
int main()
{
int tmp[9][2]={{0,0},{0,1},{0,2},{1,0},{1,2},{2,0},{2,1},{2,2}};
int m,n;
int vis[1005][1005]={0};
char map[1005][1005];
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
scanf("%s",map[i]);
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(map[i][j]=='#' && !vis[i][j])
{
if(i>=n-2 || j>=m-2)
{
printf("NO");
return 0;
}
for(int k=0;k<9;k++)
{
int nx=i+tmp[k][0];
int ny=j+tmp[k][1];
vis[nx][ny]=1;
if(map[nx][ny]!='#')
{
printf("NO");
return 0;
}
}
}
else if(map[i][j]=='#') //已被标记
{
int flag=0;
for(int k=0;k<9;k++)
{
int nx=i+tmp[k][0];
int ny=j+tmp[k][1];
if(map[nx][ny]!='#')
{
flag=1;
break;
}
}
if(!flag)
for(int k=0;k<9;k++)
{
int nx=i+tmp[k][0];
int ny=j+tmp[k][1];
vis[nx][ny]=1;
}
}
}
}
printf("YES");
return 0;