题解 P6935 【[ICPC2017 WF]Replicate Replicate Rfplicbte】

· · 题解

一道烦人、烦人、除此之外没了的题。

首先一个观察是，经过一步，原本图样的边界必然会向四个方向各扩张一格。就算有 bug 存在，四个方向上每边都至少有两个格子，仍然会保证边界扩张。

进而，回溯一步，图样的边界必然会四个方向各收缩一格。

首先忽略 bug 的存在。此时，我们尝试从后继态推回初态。手动推推即可得到 g_{i,j}=\bigotimes\limits_{u=0}^2\bigotimes\limits_{v=0}^2g_{i-u,j-v} 的 DP 式，其中 g_{i,j} 初始即为后继态的值，不在范围内的态视作 0。这样之后，矩阵左上角 (n-2)\times(m-2) 的矩阵即为初态。

假如没有 bug，则矩阵的最右两列和最下两行应该全为 0。但是因为 bug，最右两列和最下两行中可能会出现 1。

但是，我们可以根据这些 1 的分布反推出出 bug 的位置。具体而言，某个位置如果出 bug，其影响到的是以之为左上角的形如

1101101101..
1101101101..
0000000000..
1101101101..
1101101101..
0000000000..
1101101101..
..........

的部分。根据最右两列和最下两行中的 1，我们可以唯一确定该位置，或者判定其不合法。确定出锅的位置后，只需撤回其影响即可。这样，我们便实现了反推。

不断反推，直到判定无法反推，或者剩余部分的长或宽已经不大于 2，无法反推了。这样把四边压缩压缩就可以输出了。

复杂度 \min(n,m)nm。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
char s[310][310];
bool f[310][310],g[310][310];
int main(){
    scanf("%d%d",&m,&n);
    for(int i=0;i<n;i++)scanf("%s",s[i]);
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)f[i][j]=(s[i][j]=='#');
    while(n>=3&&m>=3){
        for(int i=0;i<n;i++)for(int j=0;j<m;j++){
            g[i][j]=0;
            for(int p=0;p<3;p++)for(int q=0;q<3;q++)if(i>=p&&j>=q)g[i][j]^=g[i-p][j-q];
            g[i][j]^=f[i][j];
        }
//      for(int i=0;i<n;i++,puts(""))for(int j=0;j<m;j++)printf("%d",f[i][j]);puts("");
//      for(int i=0;i<n;i++,puts(""))for(int j=0;j<m;j++)printf("%d",g[i][j]);puts("");
        bool fd=false;
        for(int i=0;i<3;i++)for(int j=0;j<3;j++){
            bool ok=true;
            int x,y;
//          printf("QWQ:%d,%d\n",i,j);
            for(int p=n+1-i,sta=true;ok;p-=3){
//              printf("%d,%d\n",p,sta);
                if(p<0&&sta)sta=false,x=p+3;
                if(sta)for(int u=0;u<3;u++)for(int v=0;v<2;v++)
                    if(p+u>=0&&p+u<n&&g[p+u][m-2+v]!=(u!=2&&(j+v)%3!=2))sta=false,x=p+3;
                if(!sta)for(int u=0;u<3;u++)for(int v=0;v<2;v++)
                    if(p+u>=0&&p+u<n&&g[p+u][m-2+v])ok=false;
                if(p<0)break;
            }
            if(!ok)continue;
            for(int q=m+1-j,sta=true;ok;q-=3){
//              printf("%d,%d\n",q,sta);
                if(q<0&&sta)sta=false,y=q+3;
                if(sta)for(int u=0;u<2;u++)for(int v=0;v<3;v++)
                    if(q+v>=0&&q+v<m&&g[n-2+u][q+v]!=((i+u)%3!=2&&v!=2))sta=false,y=q+3;
                if(!sta)for(int u=0;u<2;u++)for(int v=0;v<3;v++)
                    if(q+v>=0&&q+v<m&&g[n-2+u][q+v])ok=false;
                if(q<0)break;
            }
            if(!ok)continue;
//          printf("QQQ:%d,%d\n",x,y);
            for(int p=x;p<n;p++)for(int q=y;q<m;q++)if((p-x)%3!=2&&(q-y)%3!=2)g[p][q]^=1;
            fd=true;break;
        }
        if(!fd)break;
        n-=2,m-=2;
        for(int i=0;i<n;i++)for(int j=0;j<m;j++)f[i][j]=g[i][j];
    }
    int L=0,R=n-1,U=m-1,D=0;
    while(L<R){bool ok=true;for(int t=D;t<=U;t++)if(f[L][t]){ok=false;break;}if(!ok)break;L++;}
    while(L<R){bool ok=true;for(int t=D;t<=U;t++)if(f[R][t]){ok=false;break;}if(!ok)break;R--;}
    while(D<U){bool ok=true;for(int t=L;t<=R;t++)if(f[t][D]){ok=false;break;}if(!ok)break;D++;}
    while(D<U){bool ok=true;for(int t=L;t<=R;t++)if(f[t][U]){ok=false;break;}if(!ok)break;U--;}
    if(L==R&&U==D){puts("#");return 0;}
    for(int i=L;i<=R;i++,putchar('\n'))for(int j=D;j<=U;j++)putchar(f[i][j]?'#':'.');
    return 0;
}