• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

CF1059B Forgery

开发技术 开发技术 3小时前 1次浏览

如果纯暴力做的话,最多的格子数有(1000*1000=1e6),每一个格子都有染色和不染色两种,一共要枚举(2^{1e6})种情况,肯定会T,,

本题的特殊性在于如果对一个格子进行染色操作A,如果染色过后与想要的最终结果不冲突,那么这个操作A一定是对的,就是不存在反悔的问题(就是后面某一个染色操作出现冲突还可能会回溯回来改变操作A让其不染色),所以只需要从上到下对矩阵遍历一遍,对比着目标矩阵看每一个格子是否要染色,最后把两个矩阵对比一遍就行了,复杂度(O(nm))

#include<iostream>
#include<cstdio>

using namespace std;

const int N = 1010;

char g[N][N], st[N][N];
int n, m;
int cnt;

int main(){
    scanf("%d%d", &n, &m);
    
    for(int i = 0; i < n; i ++) scanf("%s", g[i]);
    
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
            st[i][j] = '.';
    

    for(int i = 1; i < n - 1; i ++)
        for(int j = 1; j < m - 1; j ++){
            int flag = 1;
            for(int u = -1; u <= 1; u ++)
                for(int v = -1; v <= 1; v ++){
                    if(u || v)
                        flag &= (g[i + u][j + v] == '#');
                }
            
            if(flag)
                for(int u = -1; u <= 1; u ++)
                    for(int v = -1; v <= 1; v ++)
                        if(u || v) st[i + u][j + v] = '#';
        }
            
        
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < m; j ++)
                if(st[i][j] != g[i][j]){
                    puts("NO");
                    return 0;
                }
                
        puts("YES");
        return 0;
}

程序员灯塔
转载请注明原文链接:CF1059B Forgery
喜欢 (0)