1 条题解
-
1
如果四个边界上没有格子被染色，是一个经典套路，考虑构造“梳子”状的图案，如图 1：
因为任意两个限制颜色的格子不八联通，这种方案一定是可行的。
然后考虑如果边界上有限制颜色的格子。若边界上存在形如
BWBW的序列，是一定无解的，如图 2（格子上有“限制”二字表示这个格子颜色固定）：
对于不存在形如
BWBW序列的情况，不难发现，我们一定可以找到完整的一个边界（上/下/左/右），这条边上可以全部赋成同一个颜色，而且它对面那条边界上至少有一个点是不同的颜色。不妨把这个完整的边界上的颜色当成蓝色，参考图 1 “梳子”型构造的蓝色部分，给它安排好。以保证蓝色的格子相互之间可以连通了。现在处理红色格子，可以列举出如下三个不合法的情况，我们一一解决：- 边框被蓝色包围了，部分边框上的红色与梳子的条纹不联通。
- 接近边框位置（第 和第 行）的格子不联通。
- 红色梳子条纹不联通。
图 3 的三个例子分别对应了上面的三种不合法情况：
实际上这三种情况都可以通过简单的调整实现：
- 把下面也变成蓝色。（显然）
- 直接把道路打通就可以了，因为旁边的蓝色一定是连通的（考虑
BWBW情况已经没有了，如果不联通就扩充直到顶到一个限制红色的格子门口）。 - 打穿一个蓝色条纹即可，这一步在实现情况二之后进行，就无需考虑被打穿的蓝色条纹左右不联通了（两边的条纹会沿着一条边界连起来）。
此外还有很多零零散散的细节，例如解决这三种情况的顺序，等等。
代码（长代码注意）
#include<bits/stdc++.h> #define int long long using namespace std; bool Begin; const int max_n=502; inline int read(){ int x=0;bool w=0;char c=getchar(); while(c<'0' || c>'9') w|=c=='-',c=getchar(); while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return w?-x:x; } inline void write(int x){ putchar(x==2?'B':'W'); } inline int reads(){ char c=getchar(); while(c!='B' && c!='W' && c!='.') c=getchar(); if(c=='B') return 2; if(c=='W') return 3; return 0; } int n,m,cntr; int a[max_n][max_n],ans[max_n][max_n]; int Tmp[max_n][max_n]; inline void rotate(){ for(register int i=1;i<=n;++i) for(register int j=1;j<=m;++j) Tmp[i][j]=a[i][j]; for(register int i=1;i<=n;++i) for(register int j=1;j<=m;++j) a[j][n-i+1]=Tmp[i][j]; for(register int i=1;i<=n;++i) for(register int j=1;j<=m;++j) Tmp[i][j]=ans[i][j]; for(register int i=1;i<=n;++i) for(register int j=1;j<=m;++j) ans[j][n-i+1]=Tmp[i][j]; swap(n,m),++cntr; } inline void clear(){ cntr=0; for(register int i=0;i<=n;++i) for(register int j=0;j<=m;++j) a[i][j]=ans[i][j]=a[j][i]=ans[j][i]=0; } inline int calc(){ int res=0; for(register int p=1;p<=2;++p){ for(register int i=2;i<=m;++i) if(!ans[1][i]) ans[1][i]=ans[1][i-1]; for(register int i=2;i<=n;++i) if(!ans[i][m]) ans[i][m]=ans[i-1][m]; for(register int i=m-1;i;--i) if(!ans[n][i]) ans[n][i]=ans[n][i+1]; for(register int i=n-1;i;--i) if(!ans[i][1]) ans[i][1]=ans[i+1][1]; if(!ans[1][1]) ans[1][1]=2; } for(register int i=2;i<=m;++i) if(ans[1][i]!=ans[1][i-1]) ++res; for(register int i=2;i<=n;++i) if(ans[i][m]!=ans[i-1][m]) ++res; for(register int i=m-1;i;--i) if(ans[n][i]!=ans[n][i+1]) ++res; for(register int i=n-1;i;--i) if(ans[i][1]!=ans[i+1][1]) ++res; return res; } inline bool Nice(){ bool ok=0; for(register int i=1;i<=n;++i){ if(ans[i][1]!=ans[1][1]) return 0; if(i>1 && i<n && ans[i][m]!=ans[1][1]) ok=1; } return ok; } int Red,Blue; inline void findroad(int x,int y){ if(ans[x-1][y]==Red || ans[x+1][y]==Red || ans[x][y+1]==Red) return; int X1=(x==2?1:n); if(y<=m-2 && ans[X1][y+2]==Red){ ans[X1][y]=ans[X1][y+1]=Red; return; } int X2=(x==2?2:n-1); if(y<=m-2 && ans[X2][y+2]==Red){ ans[X2][y+1]=Red; return; } int X3=(x==2?3:n-2),X4=(x==2?4:n-3); if(a[X4][y]!=Blue){ ans[X3][y]=Red; return; } int Y=(y<=m-2?y+1:y-1); ans[X2][Y]=ans[X3][Y]=Red; } inline void bigroad(int x){ for(register int j=2;j<=4;++j){ bool ok=1; for(register int i=x-1;i<=x+2;++i) if(a[i][j]==Blue){ ok=0; break; } if(ok){ ans[x][j]=ans[x+1][j]=Red; return; } } for(register int i=x-1;i<=x+2;++i) if(!a[i][3]) ans[i][3]=Red; if(a[x-1][3]){ ans[x-1][2]=Blue, ans[x][4]=Red; } if(a[x+2][3]){ ans[x+2][2]=Blue, ans[x+1][4]=Red; } if(a[x][3] || a[x+1][3]){ ans[x][2]=ans[x+1][2]=Red; } } inline void buildroad(){ int fr=0,ls=0; for(register int i=1;i<=n;++i) if(ans[i][m]==Red){ if(!fr) fr=i; ls=i; } if(!fr || (ls>3 && fr<n-2)) return; if(ls<=3 && a[4][m-1]==Blue){ ans[3][m]=ans[4][m]=ans[5][m]=Red; return; } if(fr>=n-2 && a[n-3][m-1]==Blue){ ans[n-4][m]=ans[n-3][m]=ans[n-2][m]=Red; return; } int x=(ls<=3?2:n-2); for(register int i=x;i<=x+1;++i) for(register int j=m-1;j<=m;++j) if(!a[i][j]) ans[i][j]=Red; } bool End; #define File "" signed main(){ // #ifndef ONLINE_JUDGE // freopen(File ".in","r",stdin); // freopen(File ".out","w",stdout); // #endif for(register int T=read();T;--T,clear()){ n=read(),m=read(); for(register int i=1;i<=n;++i) for(register int j=1;j<=m;++j) a[i][j]=ans[i][j]=reads(); int tmp=calc(); if(tmp>=4){ puts("NO"); continue; } if(tmp>0) while(!Nice()) rotate(); Blue=ans[1][1],Red=Blue^1; for(register int i=2;i<n;++i) for(register int j=2;j<m;++j) if(!a[i][j]) ans[i][j]=(i%4>1?Blue:Red); for(register int i=1;i<n;++i) if(ans[i][m-1]==ans[i+1][m] && ans[i+1][m-1]==ans[i][m] && ans[i][m]!=ans[i+1][m]){ if(!a[i][m]) ans[i][m]^=1; else ans[i+1][m]^=1; } buildroad(); for(register int i=2;i<m;++i){ if(a[2][i]==Red) findroad(2,i); if(a[n-1][i]==Red) findroad(n-1,i); } for(register int i=6;i<=n-6;i+=4) if(ans[i][m]==Blue || ans[i+1][m]==Blue) bigroad(i); while(cntr%4!=0) rotate(); puts("YES"); for(register int i=1;i<=n;++i){ for(register int j=1;j<=m;++j) write(ans[i][j]); putchar('\n'); } } return 0; }
- 1
