QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#273223 | #5070. Check Pattern is Bad | sio_ | TL | 3745ms | 3620kb | C++14 | 4.7kb | 2023-12-02 22:10:32 | 2023-12-02 22:10:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,no-stack-protector,fast-math",3)
int t,n,m,k,cnt;
char a[105][105],tmp[105][105];
struct node{int x,y;}v[100005];
char p[2]={'B','W'};
int dx[8]={0,0,1,1,1,-1,-1,-1};
int dy[8]={1,-1,0,1,-1,0,1,-1};
void output()
{
// if(t==10000) return ;
cout<<"YES\n";
for(int i=1;i<=n;i++,cout<<"\n")
for(int j=1;j<=m;j++) cout<<tmp[i][j];
}
queue<node> q;
char check(int x,int y)
{
char ans1='?',ans2='?',ans3='?',ans4='?';
// cout<<"xsa";
// cout<<ans1<<" "<<ans2<<" "<<ans3<<" "<<ans4<<"\n";
if(x>1&&y>1&&tmp[x-1][y-1]=='B'&&tmp[x-1][y]=='W'&&tmp[x][y-1]=='W') ans1='B';
else if(x>1&&y>1&&tmp[x-1][y-1]=='W'&&tmp[x-1][y]=='B'&&tmp[x][y-1]=='B') ans1='W';
else ans1='?';
if(x>1&&y<m&&tmp[x-1][y]=='B'&&tmp[x-1][y+1]=='W'&&tmp[x][y+1]=='B') ans2='W';
else if(x>1&&y<m&&tmp[x-1][y]=='W'&&tmp[x-1][y+1]=='B'&&tmp[x][y+1]=='W') ans2='B';
else ans2='?';
if(x<n&&y>1&&tmp[x][y-1]=='B'&&tmp[x+1][y-1]=='W'&&tmp[x+1][y]=='B') ans3='W';
else if(x>1&&y<m&&tmp[x][y-1]=='W'&&tmp[x+1][y-1]=='B'&&tmp[x+1][y]=='W') ans3='B';
else ans3='?';
if(x<n&&y<m&&tmp[x+1][y+1]=='B'&&tmp[x+1][y]=='W'&&tmp[x][y+1]=='W') ans4='B';
else if(x<n&&y<m&&tmp[x+1][y+1]=='W'&&tmp[x+1][y]=='B'&&tmp[x][y+1]=='B') ans4='W';
else ans4='?';
if(ans1=='?'&&ans2=='?'&&ans3=='?'&&ans4=='?') return '?';
else if(ans1!='B'&&ans2!='B'&&ans3!='B'&&ans4!='B') return 'B';
else if(ans1!='W'&&ans2!='W'&&ans3!='W'&&ans4!='W') return 'W';
else return '!';
}
bool cmp(node a,node b){return a.x+a.y<b.x+b.y;}
int main()
{
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
srand(time(0));
cin>>t;
for(int l=1;l<=t;l++)
{
cin>>n>>m;
cnt=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
if(a[i][j]=='?') v[++cnt]={i,j};
}
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) tmp[i][j]=a[i][j];
int flag=0;
for(int i=1;i<=cnt;i++)
{
if(check(v[i].x,v[i].y)!='?'&&check(v[i].x,v[i].y)!='!') tmp[v[i].x][v[i].y]=check(v[i].x,v[i].y);
else continue;
}
for(int c=1;c<=800&&flag==0;c++)
{
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) tmp[i][j]=a[i][j];
for(int i=1;i<=cnt;i++)
{
if(tmp[v[i].x][v[i].y]!='?') continue;
int f=0;
char ans=check(v[i].x,v[i].y);
if(ans=='!'){tmp[v[i].x][v[i].y]='B';break;}
if(ans=='?') tmp[v[i].x][v[i].y]=p[rand()%2];
else tmp[v[i].x][v[i].y]=ans;
}
for(int i=1;i<=cnt;i++)
{
if(tmp[v[i].x][v[i].y]!='?') continue;
int f=0;
char ans=check(v[i].x,v[i].y);
if(ans=='!'){tmp[v[i].x][v[i].y]='B';break;}
if(ans=='?') tmp[v[i].x][v[i].y]=p[rand()%2];
else tmp[v[i].x][v[i].y]=ans;
}
for(int i=1;i<=cnt;i++)
{
if(tmp[v[i].x][v[i].y]!='?') continue;
int f=0;
char ans=check(v[i].x,v[i].y);
if(ans=='!'){tmp[v[i].x][v[i].y]='B';break;}
if(ans=='?') tmp[v[i].x][v[i].y]=p[rand()%2];
else tmp[v[i].x][v[i].y]=ans;
}
int f=0;
for(int i=1;i<n;i++)
for(int j=1;j<m;j++)
if(tmp[i][j]==tmp[i+1][j+1]&&tmp[i][j+1]==tmp[i+1][j]&&tmp[i][j]!=tmp[i][j+1]) f=1;
// for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(f==0&&tmp[i][j]=='?')
// {
// f=1;
// cout<<n<<" "<<m<<"\n";
// for(int i=1;i<=n;i++,cout<<"\n") for(int j=1;j<=m;j++) cout<<a[i][j];
// for(int i=1;i<=n;i++,cout<<"\n") for(int j=1;j<=m;j++) cout<<tmp[i][j];
// for(int i=0;i<v.size();i++) cout<<'('<<v[i].x<<","<<v[i].y<<")"<<" ";
// cout<<"\n";
// cout<<check(i,j)<<"\n";
// for(int i=1;i<=n;i++,cout<<"\n") for(int j=1;j<=m;j++) cout<<tmp[i][j];
// }
if(f==1) continue;
flag=1;
output();
break;
}
if(flag==0) cout<<"NO\n";
}
}
/*
5
2 6
??????
W???B?
2 6
??????
W???B?
2 6
??????
W???B?
5 10
?WW????W??
BW?W???WBW
BW??WB????
???W??????
?W????B???
5 10
?WW????W??
BW?W???WBW
BW??WB????
???W??????
?W????B???
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3540kb
input:
3 2 2 ?? ?? 3 3 BW? W?B ?BW 3 3 BW? W?W ?W?
output:
YES BW WW NO YES BWB WWW WWB
result:
ok ok (3 test cases)
Test #2:
score: 0
Accepted
time: 564ms
memory: 3564kb
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 ...
output:
YES BB BW WW WW BW BB BW WW BB YES WB BB BB BW WW BW NO NO YES B W B B B W W W B W YES BBWW WWWB WWWB BBWW WWWW WWBW WWWW WWBW WWBW WBBW YES WBW WWW BBW WWW WBW WBW WBW WWW YES W B B B YES WBBB WWWB YES BWBBBB BWWWWB YES WBWWW YES BWBBWW WWBBBB BBBWWB WWWWWW YES W YES BWB BBB WBB WBB WWB WBB BBW BWW...
result:
ok ok (10000 test cases)
Test #3:
score: 0
Accepted
time: 545ms
memory: 3620kb
input:
10000 9 6 ?B?W?W WWBBWB ?WB?BW B?W?W? WW??W? B???BW ?W?WW? W?B?B? ?W?BB? 10 1 W ? ? ? ? ? ? ? B W 9 4 ???? ???? W??? ?W?B ??WW ?BW? WW?W ??W? ??W? 3 2 ?W ?B BB 2 7 ?W?BWWB ??W???W 9 9 ?BW?WWW?W BW?WBBWWW W?W????WW W??WW??WW W?BWB?B?W ??BB?WWWW W???WBW?W WWW???WWW B?WWWWWW? 8 10 W??BWWW??B ?BWBWBW?BW...
output:
NO YES W B B W W B B W B W YES BBWW BWWW WWBB BWWB BBWW WBWW WWWW WBWW WBWW YES BW BB BB YES BWWBWWB BBWBBWW NO NO YES WWB BWW BBB WBW WWW YES BWBWWWBBW WWWWBWBBB WBBBBBBBW WWWWBBBBB BWBBBWWWW BWBBWWWWW WWWWWWWWW YES WBWWBWB WBBWWWB WWBWWWW BWWWWWB BBBBWWB WBWBWBB WWWBWWB WWWWWWW BWWWBWW YES WW WW B...
result:
ok ok (10000 test cases)
Test #4:
score: 0
Accepted
time: 547ms
memory: 3516kb
input:
10000 7 7 ?B??BBW ????BB? WBBB??B WW?B??? ?B??BBB BBWB??B B???BB? 10 6 W?WW?? W??W?? ?WWWW? ?WW?WW WW??W? W????? W?WW?? WW???W WWW??W ?W??W? 2 6 ?B??W? B???BB 1 8 ??BWB?W? 5 2 WB W? B? BB ?W 7 5 W???? ?WW?? ???W? WWWW? W?W?W ?W?B? W?WWB 8 5 B?WBW B??WW WWW?B WBBWB BW?WW B?W?B ??WWB BBW?B 10 4 WWWW ?...
output:
YES BBWBBBW WBBBBBB WBBBBBB WWBBBBW BBBBBBB BBWBBBB BBWBBBW YES WWWWBB WWBWBW BWWWWW WWWBWW WWBBWB WWBWWW WWWWBW WWWBBW WWWBWW WWWBWW YES WBBWWW BBWWBB YES BWBWBWWW YES WB WB BB BB WW YES WBBWB WWWWW WWWWB WWWWW WBWWW WWWBB WBWWB NO YES WWWW BBWW WBBW WBWW WWWW BWBW WWBB WWWW WBWW BBWB YES BWWBBB BB...
result:
ok ok (10000 test cases)
Test #5:
score: 0
Accepted
time: 544ms
memory: 3476kb
input:
10000 1 1 ? 7 9 W?WB????B ?WB??B??W BBB?W?WB? WWW??WWW? WW?B??W?W ?BWW??WWW B?WW?W?WB 3 7 ??BBBB? BW?WW?? B??B?BW 1 6 ?B?WWB 7 1 W W W B ? W ? 8 8 WW??W?B? WWW????? BB??WWWW ?W???WBW BBW???WB BWBWBWW? ?W?WW??B BB?????W 10 8 WWW?W?BW WB?W?WBW WW?W?WBW WWWW?WW? WBWB?B?W BW?BW??B ??WWBWWB W?BW?BWW W?W?...
output:
YES B YES WWWBWBWBB BWBBBBBBW BBBBWBWBB WWWBWWWWW WWWBBBWBW BBWWWBWWW BWWWWWWWB YES BBBBBBB BWWWWBW BWBBWBW YES WBBWWB YES W W W B B W W NO NO YES WBBBBBB NO YES WBB WWB BBB WBB BBB BBB BBB NO YES BBB BWB WWW BBB WBW BBW WBB BBW BBB BWB YES WW BB BB WW WB BB BB NO YES BB BB BW BB BB BB BB BB NO YES ...
result:
ok ok (10000 test cases)
Test #6:
score: 0
Accepted
time: 560ms
memory: 3564kb
input:
10000 9 1 W B ? B W W ? W B 1 10 W??????BWB 5 8 ??W??WB? ?B?WWB?W ??????B? BB??BBBB WB??BBB? 6 2 ?B ?? WB ?B WW W? 1 10 WW??BW?BW? 4 3 BW? ??? B?B ??W 10 10 WW?BBW?BW? WW?BW????? ?WWBW?WB?W ???B?BBBBB ??BBBB?BBW ?WW??W?WBB W??BB?WBBB BBWBW?WBBW ?W????BWB? ??BW??WBWB 1 6 ??B??? 6 5 WBB?W ?WWWW WWWW? ...
output:
YES W B W B W W B W B YES WWBBWWBBWB YES BBWWWWBW WBWWWBBW BBBBWWBB BBBBBBBB WBBBBBBB YES WB BB WB BB WW WW YES WWBBBWWBWW YES BWB BWB BWB BWW NO YES WBBBBW NO YES B B B B B B B W B YES WWWWWWBWW WWWWWWBWB WWWWBBBBB WBWWWWWWW WWWWWBWWB WWWWWWWWW BWWWWWBWW WWWWBWWWW YES WBBW WWWW WWWB BBWB BWWW BWWW ...
result:
ok ok (10000 test cases)
Test #7:
score: 0
Accepted
time: 3745ms
memory: 3472kb
input:
10000 10 10 ?W?WW?W??W ?BWBW?BBWW ?BB?WWW?W? W?B?WWWWWW ?BWW?WWW?W BWWWWWWW?W WBBWW??B?? W??WW?W??W WWWW?WW?W? ?W?BWW?WW? 10 10 WB?WBBWWWB ?WWWW?WB?? ?B?BWW?BW? WBWBW??W?W B?WB?WBWWB WWBWBBWW?? ??WBBWBWBW WWB??WWBWB B?BWWWWBWW WW?WWWBWWB 10 10 ??W????WW? ?WW?W???W? ??W??WW?W? WW??WW?WW? ?W??WW?WW? ?...
output:
NO NO YES BWWWWBWWWB BWWBWBBBWB WWWBWWWBWB WWBBWWWWWW WWBBWWBWWW WWWBWWWWWW BWBBBBWBBW BWWWWWWWBW BWBWBWBWBB BWWWBBBBBW NO YES BBBBWBBWWB WWWBBBBBWB BWBBWWBWWW BBBBWWBBBW WBBBBWBBWW BBBBBBBWWB BBWBWWBBBB BBWBBWBWBB WBBBBBBWWB WWBWWWBBWW YES BBWBBBWBBB BBWWWBBBBB BWWBBBBBBB BBBBWBBBBB BBBBBBBWBB BBWB...
result:
ok ok (10000 test cases)
Test #8:
score: 0
Accepted
time: 3622ms
memory: 3528kb
input:
10000 10 10 ?BBBBWBBB? ??W???WB?? BB?W???BB? ?B???BBB?? W??BB?WBBB ?B?B???W?W ?????BB??? ?BW???B??? ???BBB??BB BWBBBBBBB? 10 10 BWW?WWB?BW ??B?WBBBWB B??BB??BWB BW?BWB???W ?WB?WWW?W? B??B??W?BB ?WBB?WBB?B BB??BBWBW? WB??WBB?BW ?B???B?W?? 10 10 ??WWWB??BB ?WW???WBWW ???W??W?WW ?W?B?W?W?? WWB?WBB??W B...
output:
YES WBBBBWBBBW WBWWWWWBWW BBWWWWBBBB BBBBBBBBWW WWBBBWWBBB BBBBWWWWWW BBBBWBBWWB WBWBBBBBWB WWWBBBWBBB BWBBBBBBBW NO YES BWWWWBBBBB WWWBWWWBWW BBWWWWWWWW WWWBWWWWWB WWBBWBBWWW BWWBWBBWWW WWWWWWWWWW WWWWBBWWWW WBWWWBBWBW WBBWWWBWBB YES BWBWWWBBWW WWWWWWWWWB WWBWWBWWBB WWBWWWWWWW WWWWWBWWWW WWWWBBBWWW...
result:
ok ok (10000 test cases)
Test #9:
score: 0
Accepted
time: 33ms
memory: 3564kb
input:
10000 1 100 WWW?BWB?BB?BBW?BWBB?W??B?B?BWWBWB?WWB??BBBBB??BBBBB?BBBWBWWW?B?BBBWW??BBBW???B???W??W??BW?B?B?W??WB? 1 100 ?WBW?WB?BBBB?BWBWB???WWB?BBB?BBW?B?B??W?B??BBW??WBBW???WW?BBBB?WWB?WBB???WBBB?BBW?W??BW?B??BBBBBBBWB 1 100 W?????BBB?BB?BB?????BWWWB?B???BB??????B??BWW???B??B?B???????BBB??B?BBB???B...
output:
YES WWWWBWBWBBWBBWBBWBBBWBBBBBWBWWBWBBWWBBWBBBBBBBBBBBBBBBBWBWWWWBWBBBWWBBBBBWWBWBBWWWBBWWWBWBBWBBWWWWBW YES WWBWWWBWBBBBWBWBWBWWBWWBBBBBBBBWBBBBWBWWBWWBBWWBWBBWWBBWWWBBBBBWWBWWBBBBBWBBBWBBWWWWBBWBBWWBBBBBBBWB YES WBBBBBBBBBBBBBBWWBBWBWWWBWBWWBBBWWWWBBBWWBWWWBBBWBBWBBBWBBBWBBBWWBBBBBWWWBBWBWWWWWBWWB...
result:
ok ok (10000 test cases)
Test #10:
score: 0
Accepted
time: 56ms
memory: 3572kb
input:
10000 100 1 W B B ? B B B ? B B B B W B B B ? ? B ? B B ? W B W ? B ? B W W ? W ? B ? B B ? W W B ? B B ? ? W W B B ? B B ? B ? ? ? W B W B ? B W ? ? B B B B ? B ? W B B W B ? W B B ? B B ? B ? W ? B ? B B ? B W 100 1 ? W ? W ? W W W W W B W ? ? B B ? W ? B W W W W ? ? ? ? W W B W W W W W ? W W W ? ...
output:
YES W B B W B B B W B B B B W B B B W B B B B B B W B W B B B B W W W W B B B B B W W W B B B B B B W W B B W B B W B B B W W B W B B B W W B B B B B W B W W B B W B B W B B B B B W B W W B B W B B B B W YES W W W W W W W W W W B W W W B B W W W B W W W W W W B B W W B W W W W W B W W W B W B W B B ...
result:
ok ok (10000 test cases)
Test #11:
score: -100
Time Limit Exceeded
input:
1000 100 10 WWWB?WWW?W W????????W WB?W??WW?W WBB?WWW??B ?WWWW?WW?W ?WWWW?W?WB ?B??W?W??? WW?W?BWWW? WW?B?W?W?W ????WW??W? BWB??WWWW? W??W??WW?? W?WBB??WWW ?WWBBWW?WW ?WBWW?B??? ???WWW???W ??WW?WWW?? ????W?BW?W ???W?W?W?W ?WW?WW?WB? BW??WW?WW? WB?WWWWW?W ??BWW??W?W W??B?WWWW? WWW?W??WWW BBBW??W?W? ??...
output:
NO NO NO NO NO NO NO YES WBWBWWWBBW WBWWWWWWWW WBBWWWWWWW WWWWWWWWWW BBBWBWWWWB WWWWWWWWWW WWWWBWWWWW WBWWWWWWWW WWWBWWBWBW BBWWWWBWBW BWWBBBBWBW BBWWWWWWWW BWWBWBBBBW BWWWWBWWWW WWWWWWWWBB WWWBBBWWWW WWWWWWWWWW WWWBWWWWBW WWWBWWWWWW WWWBWBBWBW BBWBWWWWBW WWWWWBWBBW WBBWWBWBWW WWWWWWWWWW WBBWWWWWBW ...