RT 预计很多都会写不完，而且很多题都不会发题解。。
https://www.cnblogs.com/Master-Yoda/p/12547799.html感觉这个写的不错orz
「JOISC 2020 Day4」传奇团子师傅
#include<bits/stdc++.h>
using namespace std;
#define fp(i,l,r) for(register int (i)=(l);i<=(r);++(i))
#define fd(i,l,r) for(register int (i)=(l);i>=(r);--(i))
#define fe(i,u) for(register int (i)=front[(u)];(i);(i)=e[(i)].next)
#define mem(a) memset((a),0,sizeof (a))
#define O(x) cerr<<#x<<':'<<x<<endl
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
void wr(int x){
if(x<0)putchar('-'),x=-x;
if(x>=10)wr(x/10);
putchar('0'+x%10);
}
const int MAXN=505,MAXM=1e6+10;
const int fx[]={-1,-1,0,1},fy[]={0,1,1,1};
char mp[MAXN][MAXN];
int id[MAXN][MAXN][4],res,cnt,resm,n,m;
bool sta[MAXM],stam[MAXM];
vector<int>G[MAXM];
inline void adde(int u,int v){if(u!=v)G[u].push_back(v);}
inline bool check(int x,int y){return x>=1&&y>=1&&x<=n&&y<=m;}
inline void construct(){
fp(i,1,n){
fp(j,1,m)if(mp[i][j]=='W'){
fp(k,0,3){
int x1=i+fx[k],y1=j+fy[k],x2=i-fx[k],y2=j-fy[k];
if(!check(x1,y1)||!check(x2,y2))continue;
if(mp[x1][y1]=='W'||mp[x2][y2]=='W'||mp[x1][y1]==mp[x2][y2])continue;
id[i][j][k]=++cnt;
}
fp(k,0,3)fp(l,0,3)if(k!=l&&id[i][j][k]&&id[i][j][l])
adde(id[i][j][k],id[i][j][l]);
}
}
fp(i,1,n){
fp(j,1,m)if(mp[i][j]=='W'){
fp(k,0,3)if(id[i][j][k]){
int x=i+fx[k],y=j+fy[k];
fp(l,0,3){
int xx=x+fx[l],yy=y+fy[l];
if(id[xx][yy][l])adde(id[i][j][k],id[xx][yy][l]);
xx=x-fx[l],yy=y-fy[l];
if(id[xx][yy][l])adde(id[i][j][k],id[xx][yy][l]);
}
x=i-fx[k],y=j-fy[k];
fp(l,0,3){
int xx=x+fx[l],yy=y+fy[l];
if(id[xx][yy][l])adde(id[i][j][k],id[xx][yy][l]);
xx=x-fx[l],yy=y-fy[l];
if(id[xx][yy][l])adde(id[i][j][k],id[xx][yy][l]);
}
}
}
}
}
inline void print(){
fp(i,1,n){
fp(j,1,m)if(mp[i][j]=='W'){
if(id[i][j][0]&&stam[id[i][j][0]])putchar('|');
else if(id[i][j][1]&&stam[id[i][j][1]])putchar('/');
else if(id[i][j][2]&&stam[id[i][j][2]])putchar('-');
else if(id[i][j][3]&&stam[id[i][j][3]])putchar('\');
else putchar('W');
}
else putchar(mp[i][j]);
putchar('
');
}
}
struct ender{
~ender(){print();}
}szqakioi;
mt19937 gen(20020328);
inline double rand01(){
return (double)gen()/4294967296;
}
main(){
freopen("input_04.txt","r",stdin);freopen("output_04.txt","w",stdout);
n=read();m=read();
fp(i,1,n)scanf("%s",mp[i]+1);
construct();
int goal=19120,fail=0;
while(res<goal){
double T=500;
while(T>1e-7){
fp(kk,1,5){
int u=gen()%cnt+1;
while(sta[u])u=gen()%cnt+1;
int delta=1;
for(const int &v:G[u])if(sta[v])--delta;
if(delta>0||rand01()<exp(1.0*delta/T)){
for(const int &v:G[u])sta[v]=0;
sta[u]=1;
res+=delta;
if(res>resm){
resm=res;memcpy(stam,sta,sizeof sta);
if(resm>=goal)return 0;
}
}
}
if(gen()%500000==0)O(res),O(resm),O(T);
T*=0.9999996;
}
memcpy(sta,stam,sizeof sta);res=resm;fail=0;
cerr<<"Failed"<<endl;
}
return 0;
}