Codeforces Round #514 (Div. 2) B

这个题我一开始没思路，最后也没思路

2个小时一直没思路

本来还想解释题意的，写了半天发现解释的不是很清楚，你还是google翻译一下吧

这个题解法是这样的：

首先，给你图案里面有很多的点，每个点的周围8个点都不可能在上面落笔，因为你一旦在周围8个点落笔，必定会覆盖掉这个点，

其次，每一个有#的地方，他周围8个点一定有一个地方能够落笔

所以我们把所有不可能落笔的点都记录下来，再判断每一个#的地方，假设周围有能落笔的地方，说明可以画

只要找到一个#周围没有可以落笔的地方，输出no

（笔不能超过纸张，也就是说落笔范围在（1，1）（n-2,m-2）这个矩形里面）

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e3+;

char arr[maxn][maxn];

bool vis[maxn][maxn];

int n,m;

void painw(int x,int y)

{

    vis[x+][y] = vis[x+][y-] = vis[x+][y+] = vis[x-][y] = vis[x-][y-] = vis[x-][y+] = false;

    vis[x][y+] = vis[x][y-] = false;

}

bool pan(int x,int y)

{

    bool f = false;

    for(int i = -;i <= ;++i)

    {

        for(int j = -; j <= ; ++j)

        {

            //cout << x+i << " " << y+j << endl;

            if(x+i <=  || x+i >= n || y+j <=  || y+j >= m)

                continue;

            if(i ==  && j == )

                continue;

            if(vis[x+i][y+j] == true)

                f = true;

        }

    }

    //cout << f << endl;

    return f;

}

int main()

{

    scanf("%d%d",&n,&m);

    int cnt = ;

    memset(vis,true,sizeof(vis));

    for(int i = ; i <= n; ++i)

    {

        getchar();

        for(int j = ; j <= m; ++j)

        {

            scanf("%c",arr[i]+j);

            if(arr[i][j] == '.')

                painw(i,j);

        }

    }

    for(int i = ; i <= m+; ++i)

        vis[][i] = vis[n+][i] = false;

    for(int i = ; i <= n+; ++i)

        vis[i][] = vis[i][m+] = false;

    /*for(int i = 0; i <=n+1; ++i)

    {

        for(int j = 0; j <= m+1; ++j)

            printf("%d",vis[i][j]);

        printf("\n");

    }*/

    for(int i = ; i <= n; ++i)

    {

        for(int j = ; j <= m; ++j)

        {

            if(arr[i][j] == '#' && pan(i,j) == false)

            {

                printf("NO\n");

                return ;

            }

        }

    }

    printf("YES\n");

    return ;

}

巴特西

Codeforces Round #514 (Div. 2) B - Forgery

最新文章

热门文章