把矩阵黑白染色,B 对应的颜色中,黑色数量和白色数量要么相等要么相差一,不是很合理吗?为啥WA2?
#include<cstdio>
using namespace std;
int t,n,cnt,rt,l,r,cnt1[2],zong,qu[400001][2],r1,r2;
char s[2][200010];
bool flg,col[2][200010],vis[200010][2];
bool lian(){
qu[++r][0]=rt/n,qu[r][1]=rt%n,vis[rt%n][rt/n]=1;
while(l<r){
r1=qu[++l][0],r2=qu[l][1];
if(r1&&s[0][r2]=='B'&&!vis[r2][0])qu[++r][0]=0,qu[r][1]=r2,vis[r2][0]=1;
if(!r1&&s[1][r2]=='B'&&!vis[r2][1])qu[++r][0]=1,qu[r][1]=r2,vis[r2][1]=1;
if(r2&&s[r1][r2-1]=='B'&&!vis[r2-1][r1])qu[++r][0]=r1,qu[r][1]=r2-1,vis[r2-1][r1]=1;
if(r2<n-1&&s[r1][r2+1]=='B'&&!vis[r2+1][r1])qu[++r][0]=r1,qu[r][1]=r2+1,vis[r2+1][r1]=1;
}
for(int i=0;i<2;++i)for(int j=0;j<n;++j)cnt+=vis[j][i];
return cnt==zong;
}
int main(){
freopen("guess.in","r",stdin),freopen("guess.out","w",stdout);
for(int i=0;i<200000;++i)col[0][i]=i&1,col[1][i]=!col[0][i];
scanf("%d",&t);
while(t--){
scanf("%d%s%s",&n,&s[0],&s[1]),zong=cnt1[0]=cnt1[1]=cnt=0,rt=l=r=-1;
for(int i=0;i<n;++i){
vis[i][0]=vis[i][1]=0;
if(s[0][i]=='B')++cnt1[col[0][i]],++zong;
if(s[1][i]=='B')++cnt1[col[1][i]],++zong;
}
for(int i=0;i<n;++i)if(s[0][i]=='B'){rt=i;break;}
if(rt==-1)for(int i=0;i<n;++i)if(s[1][i]=='B'){rt=i+n;break;}
if(!zong){printf("YES\n");continue;}
flg=lian();if(!flg){printf("NO\n");continue;}
if(cnt1[0]==cnt1[1]||cnt1[0]-cnt1[1]==1||cnt1[0]-cnt1[1]==-1)printf("YES\n");
else printf("NO\n");
}
return 0;
}