题解 UVA10572【Black & White】

xtx1092515503 · 2021-07-10 16:09:04 · 题解

一道很猛的题。

我们考虑轮廓线DP，压缩轮廓线上连通块的状态。

因为要求 2\times2 格子内部不全相同，所以我们要压缩 m+1 个格子的状态。

但是我们发现这 9 个格子中，同色格子最多可能在 5 个不同连通块中，刚好压不到 4 进制，非常烦人。

但是我们又发现，仅有这种情况下，出现 5 个连通块的状态才是合法的：

????????
o#o#o#o#
#???????

可以发现，此时假如DP状态覆盖所有非 ? 的格子，则 # 就产生了 5 个连通块。其它情况下，出现 5 个不同连通块的情形都不可能合法。

但是，我们发现，因为 # 在这之后的位置必然是联通的，所以任两个 o 都不可能联通，也就是说假如我们给所有的 # 赋上奇数表示连通块编号、o 赋上偶数表示连通块编号，则字典序最小的编号是唯一的：

????????
03050709
1???????

当然，还有一种是交换 o 与 # 得到的。

但不管哪种，我们都可以单独记录一下。

搜索，会发现所有狭义合法状态只有 5608 种。再加上出现 5 个连通块的 2 种，共计 5610 种。

这里狭义合法状态的定义：

相邻同色格子必位于同一连通块。

类似括号匹配，不存在两个连通块使得属于它们的元素在状态中交替出现。例：?0?1?0?1? 这个状态会被判不合法。

对于每种颜色，属于它的连通块数量不超过 4。（注意这条性质，这就是为什么其被称作“狭义”的原因。要想得到广义合法状态，就要再加上 5 个的两种）

连通块编号依次连接形成的字符串是所有同构串中字典序最小的。

这样之后就可以DP了。

设 f(x,y,ox,oy,id) 表示：

当前在格子 (x,y)。
当前 o 格的状态是 ox，其可以为 0/1/2，分别表示尚未出现 o 格/当前状态中有 o 格/o 格曾经出现过但现在没有了。
当前轮廓线的状态是 id。

这个时候的答案。

然后就枚举 (x,y) 填什么字符。这个字符具体应该满足如下限制：

满足格子本身强制填入字符的限制。
满足 2\times2 格子不相同的限制。
满足 ox/oy 是 2 时的限制。
填入的字符如果：
- 与其上方格子内的字符不同。
- 上方格子所在连通块仅剩此字符一个位置。
- 如果填入上方格子的字符除了该连通块以外还有其它连通块，则现在填入的字符就会阻止该连通块与其它连通块联通，也就会导致图形不可能联通。此时，该字符不合法。
- 否则，则上方连通块是唯一连通块，则上方格子中字符再往后就不可能再度出现。这时要把对应的 ox/oy 赋作 2，但填入该字符本身是合法的。

最后考虑何样的终局状态是合法的：

其可以全部由同种字符构成。
其也可以由两种字符构成，但它们必须各自属于同个连通块。

答案随便记录就行了。

细节很多很多。

代码：

#include<bits/stdc++.h>
using namespace std;
int T,sta[6010],cnt,n,m,nw[2][6010],f[9][9][3][3][6010];
void pr(int x){for(int i=0;i<=m;i++)printf("%d",(x>>i*3)&7);}
map<int,int>mp;
char s[10][10];//#1 o0
int num[20],pre[20];
void dfs1(int pos,int xb,int yb,int las,int msk){
//  for(int i=0;i<pos;i++)printf("[%d,%d]",num[i],pre[i]);puts("");
    if(pos==m+1){if(xb<8&&yb<9)sta[++cnt]=msk,mp[msk]=cnt,nw[0][cnt]=xb+2,nw[1][cnt]=yb+2;return;}
    if(las==0){
        num[pos]=num[pos-1],pre[pos]=(pre[pos-1]==-1?pos-1:pre[pos-1]);
        dfs1(pos+1,xb,yb,0,msk+(num[pos]<<3*pos));
    }else{
        num[pos]=xb+2,pre[pos]=-1;
        dfs1(pos+1,xb+2,yb,0,msk+(num[pos]<<3*pos));
        for(int j=pos-1;j>=0;j=(pre[j]==-1?j:pre[j])-1){
            if(num[j]&1)continue;
            num[pos]=num[j],pre[pos]=(pre[j]==-1?j:pre[j]);
            dfs1(pos+1,xb,yb,0,msk+(num[pos]<<3*pos));
        }
    }
    if(las==1){
        num[pos]=num[pos-1],pre[pos]=(pre[pos-1]==-1?pos-1:pre[pos-1]);
        dfs1(pos+1,xb,yb,1,msk+(num[pos]<<3*pos));
    }else{
        num[pos]=yb+2,pre[pos]=-1;
        dfs1(pos+1,xb,yb+2,1,msk+(num[pos]<<3*pos));
        for(int j=pos-1;j>=0;j=(pre[j]==-1?j:pre[j])-1){
            if(!(num[j]&1))continue;
            num[pos]=num[j],pre[pos]=(pre[j]==-1?j:pre[j]);
            dfs1(pos+1,xb,yb,1,msk+(num[pos]<<3*pos));
        }
    }
}
void decode(int id){
    if(m==8&&id==cnt-1){
        for(int i=0;i<=m;i+=2)num[i]=i;
        for(int i=1;i<=m;i+=2)num[i]=1;
        return;
    }
    if(m==8&&id==cnt){
        for(int i=0;i<=m;i+=2)num[i]=i+1;
        for(int i=1;i<=m;i+=2)num[i]=0;
        return;
    }
    int msk=sta[id];
    for(int i=0;i<=m;i++)num[i]=(msk>>i*3)&7;
}
int hs[20];
int code(){
    for(int i=0;i<=9;i++)hs[i]=-1;
    int xb=0,yb=1;
//  for(int i=0;i<=m;i++)printf("%d",num[i]);puts("");
    for(int i=0;i<=m;i++){
        if(hs[num[i]]==-1){if(num[i]&1)hs[num[i]]=yb,yb+=2;else hs[num[i]]=xb,xb+=2;}
        num[i]=hs[num[i]];
    }
//  for(int i=0;i<=m;i++)printf("%d",num[i]);puts("");
    if(xb>10||yb>11)return -1;
    if(xb==10)return yb==3?cnt-1:-1;
    if(yb==11)return xb==2?cnt:-1;
    int msk=0;
    for(int i=0;i<=m;i++)msk+=(num[i]<<i*3);
    if(mp.find(msk)==mp.end())return -1;
    return mp[msk];
}
int dfs(int,int,int,int,int);
int nex(int x,int y,int ox,int oy){
//  printf("NEX(%d,%d)\n",x,y);
//  for(int i=0;i<=m;i++)printf("%d",num[i]);puts("");
    if(!x)for(int i=y+1;i<=m;i++)num[i]=num[i-1];
    int OX=0,OY=0;
    for(int j=0;j<=m;j++){
        if(j==y+1)continue;
        if(num[j]&1)OY=1;else OX=1;
    }
    if(ox&&!OX)OX=2;
    if(oy&&!OY)OY=2;
    if(y==m-1)for(int i=m;i;i--)num[i]=num[i-1];
    return y==m-1?dfs(x+1,0,OX,OY,code()):dfs(x,y+1,OX,OY,code());
}
char res[510],*ser;
bool fd;
int dfs(int x,int y,int ox,int oy,int id){ 
    if(id==-1)return 0;
    int&r=f[x][y][ox][oy][id];if(r!=-1)return r;r=0;
//  printf("%d %d %d %d %d:",x,y,ox,oy,id);decode(id);for(int i=0;i<=m;i++)printf("%d",num[i]);puts("");
    if(x==n){
        decode(id);
        for(int i=1,xb=-1,yb=-1;i<=m;i++)if(num[i]&1){
            if(yb==-1)yb=num[i];
            if(yb!=num[i])return r=0;
        }else{
            if(xb==-1)xb=num[i];
            if(xb!=num[i])return r=0;
        }
        return r=1;
    }
    for(int i=0;i<2;i++){
        if(i==0&&(s[x][y]=='#'||ox==2))continue;
        if(i==1&&(s[x][y]=='o'||oy==2))continue;
        decode(id);
        if(!x){
//          printf("%d %d %d\n",x,y,id);
            num[y]=-1;
            if(y&&(num[y-1]&1)==i)num[y]=num[y-1];
            else{
                for(int j=y-1;j>=0;j--)if((num[j]&1)==i){num[y]=num[j]+2;break;}
                if(num[y]==-1)num[y]=i;
            }
        }else if(!y){
            if(i==(num[1]&1))num[0]=num[1];
            else{
                bool ok=false;
                for(int j=2;j<=m&&!ok;j++)ok|=(num[1]==num[j]);
                if(!ok){
                    for(int j=2;j<=m&&!ok;j++)ok|=((num[1]&1)==(num[j]&1));
                    if(ok)continue;
                }
//              printf("%d,%d:%d\n",x,y,nw[i][id]);
                num[0]=nw[i][id];
            }           
        }else{
            bool L=(num[y-1]&1),U=(num[y+1]&1);
            if(L==(num[y]&1)&&L==U&&L==i)continue;//a same-coloured square.
            if(U!=i){
                bool ok=false;
                for(int j=0;j<=m&&!ok;j++)if(j!=y&&j!=y+1)ok|=(num[y+1]==num[j]);
                if(!ok){
                    for(int j=0;j<=m&&!ok;j++)if(j!=y&&j!=y+1)ok|=((num[y+1]&1)==(num[j]&1));
                    if(ok)continue;
                }
                if(L==i)num[y]=num[y-1];
                else num[y]=nw[i][id];
            }else{
                if(L!=i||num[y-1]==num[y+1])num[y]=num[y+1];
                else{
                    for(int j=0;j<=m;j++)if(j!=y+1&&num[j]==num[y+1])num[j]=num[y-1];
                    num[y]=num[y+1]=num[y-1];
                }
            }
        }
        if(!fd){
            *ser++=(i?'#':'o');
            if(y==m-1)*ser++='\n';          
        }
        r+=nex(x,y,ox,oy);
        if(r)fd=true;
        if(!fd){
            if(y==m-1)ser--;
            ser--;
        }
    }
    return r;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        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++)putchar(s[i][j]);puts("");}
        mp.clear(),cnt=0,dfs1(0,-2,-1,-1,0);
        if(m==8)cnt+=2;
//      printf("%d\n",cnt);
//      for(int i=1;i<=cnt;i++)pr(sta[i]),puts("");puts("");
        memset(f,-1,sizeof(f)),ser=res,fd=false;
        printf("%d\n",dfs(0,0,0,0,mp[0]));
        *ser='\0',printf("%s\n",res);
    }
    return 0;
}