zcmimi's blog
查看原题

点击跳转

可以发现,每次变化后只有那些周围有与它同色的格子发生变化

也就是连通块发生变化

而每次连通块发生变化,又会并入一些单独的格子

我们只需要bfs找出每个方块什么时候被纳入连通块就可以了

查询时判断一下奇偶

#include<bits/stdc++.h>
const int N=1011,M=10000000;
int n,m,k,dx[4]={0,1,0,-1},dy[4]={1,0,-1,0},ti[N][N];
char a[N][N];
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;++i)scanf("%s",a[i]+1);
    static int p[N*N],q[N*N],h,t;
    memset(ti,60,sizeof ti);
    h=0,t=0;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j){
            bool tmp=0;
            for(int k=0;k<3;++k)
                tmp|=a[i][j]==a[i+dx[k]][j+dy[k]];
            if(tmp)p[t]=i,q[t]=j,ti[i][j]=0,++t;
        }
    while(h<t){
        int x=p[h],y=q[h++];
        for(int i=0;i<3;++i){
            int nx=x+dx[i],ny=y+dy[i];
            if(nx<1||nx>n||ny<1||ny>m)continue;
            if(ti[nx][ny]>M)
                p[t]=nx,q[t]=ny,
                ti[nx][ny]=ti[x][y]+1,
                ++t;
        }
    }
    while(k--){
        int x,y;long long tim;
        scanf("%d%d%lld",&x,&y,&tim);
        if(tim<ti[x][y])putchar(a[x][y]);
        else putchar(a[x][y]^((tim-ti[x][y])&1));
        putchar('\n');
    }
}
LG CF1349C Orac and Game of Life
comment评论
Search
search