自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

搬运于2025-08-24 22:52:39，当前版本为作者最后更新于2023-11-19 19:03:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

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

$10\mathrm{s}$ 抽象构造题。罚了 $10$ 发爽歪歪。

解法

考虑先确定可以确定的 $\texttt{?}$，就是一个 $2\times 2$ 的子矩阵，其中 $3$ 个字符已经确定，剩下那个字符只有一种填法的。实现可以枚举一个格子，使用一个方向数组枚举子矩阵，然后如果两种子矩阵在该字符上有冲突直接无解。这个过程要正着倒着做两遍！可以证明剩下的情况都是有解的。

现在我们剩下了一些格子没法确定。考虑随机化，对当前一个 $\texttt{?}$ 先随机赋一个值，然后后面的格子再根据前面已经染好色的格子进行染色（显然最开始那种构造的方法可以改一改再用），如果还是有多种选择就再随机一下。一直重复这个过程（用死循环），直到找到解了就输出。

放代码：

// 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??????