[EC Final 2021] Check Pattern is Bad 题解

· · 题解

前言

Update：原来的代码漏判了一个细节被 hack 了，现在已经修正，感谢 @Sio_ 的贡献。

## 解法 考虑先确定可以确定的 $\texttt{?}$，就是一个 $2\times 2$ 的子矩阵，其中 $3$ 个字符已经确定，剩下那个字符只有一种填法的。实现可以枚举一个格子，使用一个方向数组枚举子矩阵，然后如果两种子矩阵在该字符上有冲突直接无解。**这个过程要正着倒着做两遍**！可以证明剩下的情况都是有解的。 现在我们剩下了一些格子没法确定。考虑随机化，对当前一个 $\texttt{?}$ 先随机赋一个值，然后后面的格子再根据前面已经染好色的格子进行染色（显然最开始那种构造的方法可以改一改再用），如果还是有多种选择就再随机一下。一直重复这个过程（用死循环），直到找到解了就输出。 放代码： ```cpp // 10s...mt19937 yyds!!! #include<bits/stdc++.h> using namespace std; typedef pair<int,int> pii; const int dx[4]={-1,-1,0,0},dy[4]={-1,0,-1,0}; // 方向数组 char mp(bool b){return b?'W':'B';} int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--){ int n,m; cin>>n>>m; mt19937 g(time(0)); uniform_int_distribution<> u(0,1); vector<string> a(n); for(auto &i:a)cin>>i; auto cl=[&](int x,int y){ for(int i=0;i<4;i++){ int x0=x+dx[i],y0=y+dy[i]; if(~min(x0,y0)&&x0+1<n&&y0+1<m){ vector<pii> p={ make_pair(x0,y0), make_pair(x0+1,y0), make_pair(x0,y0+1), make_pair(x0+1,y0+1)}; // 子矩阵中四个元素 int c=0; for(auto [x1,y1]:p) if(make_pair(x1,y1)!=make_pair(x,y)&&a[x1][y1]=='?')c++; // 判断其他字符是否是 ? if(c)continue; // 该子矩阵不能确定 switch(i){ case 0: if(a[x0+1][y0]==a[x0][y0+1]&&a[x0+1][y0]!=a[x0][y0]) if(a[x][y]==a[x0][y0])return false; else a[x][y]=a[x0+1][y0]; break; // 先判矛盾然后染色 case 1: if(a[x0][y0]==a[x0+1][y0+1]&&a[x0][y0+1]!=a[x0][y0]) if(a[x][y]==a[x0][y0+1])return false; else a[x][y]=a[x0][y0]; break; case 2: if(a[x0][y0]==a[x0+1][y0+1]&&a[x0+1][y0]!=a[x0][y0]) if(a[x][y]==a[x0+1][y0])return false; else a[x][y]=a[x0][y0]; break; case 3: if(a[x0+1][y0]==a[x0][y0+1]&&a[x0+1][y0]!=a[x0+1][y0+1]) if(a[x][y]==a[x0+1][y0+1])return false; else a[x][y]=a[x0+1][y0]; break; } } } return true; }; // 染色构造，返回值为是否有矛盾 bool f=true; for(int i=0;i<n&&f;i++) for(int j=0;j<m&&f;j++)f&=cl(i,j); for(int i=n-1;~i&&f;i--) for(int j=m-1;~j&&f;j--)f&=cl(i,j); // 记得把漏下的做一遍 if(!f){cout<<"NO\n"; continue;} // 无解 while(1){ vector<string> r=a; f=true; for(int i=0;i<n&&f;i++) for(int j=0;j<m&&f;j++) if(a[i][j]=='?') if(f&=cl(i,j);a[i][j]=='?')a[i][j]=mp(u(g)); // 随机一下 for(int i=0;i<n&&f;i++) for(int j=0;j<m&&f;j++)f&=cl(i,j); // 判断解的合法性 if(f)break; a=r; } cout<<"YES\n"; for(auto i:a)cout<<i<<'\n'; } return 0; } ``` 顺便放一下 hack 掉原来的代码的 hack 数据： ``` 1 4 10 WB??WB??B? ??WB??W??B ??W?BWB??W ??BW?????? ```