QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#791025 | #5070. Check Pattern is Bad | louhao088 | ML | 0ms | 3768kb | C++23 | 1.5kb | 2024-11-28 16:29:40 | 2024-11-28 16:29:40 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
inline int read(){
char ch=getchar();int x=0;bool f=0;
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
if(f==1)x=-x;return x;
}
const int maxn=1e5+5,inf=1e6;
int n,m,a[105][105],ans,T;
int dx[4]={0,0,-1,-1},dy[4]={0,-1,0,-1};
char s[maxn];
int calc(int x,int y){
if(x==0||y==0||x==n||y==m)return 0;
return a[x][y]+a[x+1][y]+a[y+1][x]+a[x+1][y+1];
}
void dfs(int x,int y){
for(int i=0;i<4;i++){
if(abs(calc(x+dx[i],y+dy[i]))==3){
int z=a[x][y]*-1;
for(int j=0;j<4;j++)if(!a[x+dx[i]-dx[j]][y+dy[i]-dy[j]]){
a[x+dx[i]-dx[j]][y+dy[i]-dy[j]]=z;
dfs(x+dx[i]-dx[j],y+dy[i]-dy[j]);
}
}
}
}
void solve(){
n=read(),m=read();
for(int i=1;i<=n;i++){
scanf("%s",s+1);
for(int j=1;j<=m;j++){
if(s[j]=='B')a[i][j]=1;
else if(s[j]=='W')a[i][j]=-1;
else a[i][j]=0;
if((i+j)&1)a[i][j]*=-1;
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
dfs(i,j);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)if(!a[i][j]){
a[i][j]=1;dfs(i,j);
}
for(int i=1;i<n;i++)
for(int j=1;j<m;j++){
if(a[i][j]==a[i+1][j]&&a[i][j]==a[i][j+1]&&a[i][j]==a[i+1][j+1]){
puts("NO");return;
}
}
puts("YES");
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if((i+j)&1)a[i][j]*=-1;
if(a[i][j]==1)putchar('B');
else putchar('W');
}
puts("");
}
}
signed main(){
T=read();
while(T--)solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3768kb
input:
3 2 2 ?? ?? 3 3 BW? W?B ?BW 3 3 BW? W?W ?W?
output:
YES BW WW NO YES BWB WWW BWB
result:
ok ok (3 test cases)
Test #2:
score: -100
Memory Limit Exceeded
input:
10000 9 2 BB BW WW WW ?W ?B B? W? BB 6 2 ?? ?B B? BW WW ?? 10 7 WBBBW?? ???BWWW ???BWWB ??WWBW? BBWBBWB WWB?WW? BWBW??? WWWWBBW BBWBB?W B?W?W?B 4 7 ??WBWWB ?BBWWWB ?W?BBB? BBBWBBB 10 1 B W ? B B W W W B ? 10 4 ??WW W?W? WWW? ???W ?W?? ?W?W W?W? ?W?W ???W ???W 8 3 WBW W?? ??? ??? W?W W?W ??? ?W? 4 1 ...