[刷题笔记] CF1059B Forgery

Problem

Solution

搜索染色类。

我们发现染色是不可逆的，也就是染成了#后不得染回“.”,所以对于每次染色我们都要尽可能向std上靠拢。

我们可以观察一下std，发现需要尽可能从std上的“.”向四周染色（因为3*3染色中间的"."不染)。每次染色前需要判断染完这一部分是否和std一致，如果一致则可以染色（因为染色不可逆）

代码实现较易。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 1010
using namespace std;
int n,m;
char mapp[N][N],ans[N][N];
int dx[8]={0,1,1,1,0,-1,-1,-1}; //3*3八方向
int dy[8]={1,1,0,-1,-1,-1,0,1};
bool get_ans = false;
bool chk(int x,int y)
{
    for(int i=0;i<8;i++)
    {
        int ax = x+dx[i];
        int ay = y + dy[i];
        if(ax >= 1 && ax <= n && ay >= 1 && ay <= m && mapp[ax][ay] == '#') continue; 
        else return false; //如果染色的这个点越界或者std上这个点为"."则不得染色
    }
    return true;
 //   return true;
}
void full(int x,int y)
{
    for(int i=0;i<8;i++)
    {
        int ax = x + dx[i];
        int ay = y + dy[i];
        if(ax >= 1 && ax<= n && ay >= 1 && ay <= m)
            ans[ax][ay] = '#';
    }
}
bool check_ok()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) if(ans[i][j] != mapp[i][j]) return false;
    }
    return true;
}
void print()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) cout<<ans[i][j];
        cout<<endl;
    }
}
int main()
{
    memset(ans,'.',sizeof(ans));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) cin>>mapp[i][j];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(chk(i,j))
            {
              //  cout<<i<<" "<<j<<endl;
                full(i,j);
                if(check_ok()) 
                {
                    get_ans = true;
                    cout<<"YES"<<endl;
                    return 0;
                }
            }
        }
    }
    if(check_ok()) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}