CodeForces - 1059B Forgery不错 想了好久

题目链接：​​http://codeforces.com/problemset/problem/1059/B​​

B. Forgery

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

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

input

Copy

3 3
###
#.#
###

output

Copy

YES

input

Copy

3 3
###
###
###

output

Copy

NO

input

Copy

4 3
###
###
###
###

output

Copy

YES

input

Copy

5 7
.......
.#####.
.#.#.#.
.#####.
.......

output

Copy

YES

Note

In 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):

1. we have a clear paper:

...
...
...
...

1. use the pen with center at (2,2)(2,2).

###
#.#
###
...

1. 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).

题意有点难懂，英语不行，看了好久。

题意：

给你一个印章，能印出形为

###

#.#

###

#代表墨水，.代表空。

给定图案问是否能用这个印章印出目标图案，不能越界去印图案

分析：

一开始思路想歪了，去找什么才能构成错误的图案，一开始以为找到了，开始写代码，但是回来发现还有好几种呢，找了好久没发现什么规律。然后就想暴力模拟。

遍历图中每一个点，我们判断每一个（i，j）为中心点时是否能盖下印章，如果以其为中心点，四周的八个点有‘.’或者超出边界，则不能以其为中心点盖章，遍历整个图吧能盖章的地方都盖一遍，形成的图案如果和目标图案一样则输出YES，否则输出NO

代码实现：

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef long long ll;
const int N = 1010;
int a[N][N];
ll n,m;
bool ju(int x,int y)
{
    int num=0;
    for(int i=-1;i<=1;i++)
        for(int j=-1;j<=1;j++)
    {
        if(i==0&&j==0) continue;
        if(a[x+i][y+j]==1||a[x+i][y+j]==2)///下面a有的改成了2
            num++;
    }

    if(num==8)
    {
     for(int i=-1;i<=1;i++)
        for(int j=-1;j<=1;j++)
       {
        if(i==0&&j==0) continue;
        a[x+i][y+j]=2;
       }
    }
}
int main(){
 
   
    while (~scanf("%lld%lld", &n, &m) )
    {
        string s;
        cin.get();
        for(int i=1;i<=n;i++)
        {
             cin>>s;
             for(int k=0;k<m;k++)
             {
                if(s[k]=='#')
                 a[i][k+1]=1;
                else
                 a[i][k+1]=0;
                 //cout<<a[i][k+1]<<endl;
             }
        }
        int flag=0;
        for(int i=2;i<n;i++)
          for(int j=2;j<m;j++)
        {
          ju(i,j);
        }
        for(int i=1;i<=n;i++)
        {
        for(int j=1;j<=m;j++)
            {
            // cout<<a[i][j]<<" ";
                if(a[i][j]==1)
                  {  
                   flag=1;
               //   break;
                  }
            } 
        if(flag==1) break;
        //cout<<endl;
        }
        if(flag==0)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
 
    return 0;
}