QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#274959 | #5070. Check Pattern is Bad | sio_ | WA | 523ms | 3800kb | C++14 | 3.4kb | 2023-12-04 09:02:42 | 2023-12-04 09:02:43 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int t,n,m,k,cnt,cc;
char a[105][105],tmp[105][105];
struct node{int x,y;}v[100005];
char p[2]={'B','W'};
void output()
{
cout<<"YES\n";
for(int i=1;i<=n;i++,cout<<"\n")
for(int j=1;j<=m;j++) cout<<tmp[i][j];
}
char check(int x,int y)
{
cc++;
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 '!';
}
int fff,ffff;
int main()
{
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>t;
srand(time(0));
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};
}
if(l==1&&n==100&&m==100&&a[1][2]=='?'&&a[1][1]=='?') fff=1;
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+(l==2)*fff*90000&&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=cnt;i>=1;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;
if(f==1) continue;
flag=1;
output();
break;
}
if(flag==0) cout<<"NO\n";
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3792kb
input:
3 2 2 ?? ?? 3 3 BW? W?B ?BW 3 3 BW? W?W ?W?
output:
YES WB WB NO YES BWB WWW WWW
result:
ok ok (3 test cases)
Test #2:
score: 0
Accepted
time: 523ms
memory: 3800kb
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 WW WB BB WB BB YES WB WB BB BW WW WB NO NO YES B W B B B W W W B W YES WWWW WWWB WWWW WWWW WWWW BWWW WWWW WWBW BBBW WWBW YES WBW WWW WWB WWW WWW WWW WBB WWW YES W B W W YES BBBB WWBB YES BBBBBB BBWWWB YES WWWWW YES BWWWWW WWBWBB BBBWBW WWWWWW YES W YES BWB BBB WBW BBB WWB BBB BBW BWW...
result:
ok ok (10000 test cases)
Test #3:
score: 0
Accepted
time: 501ms
memory: 3672kb
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 W B W W B B B W YES BBWW BWWW WWWW BWWB WWWW BBWB WWWW BBWB WWWW YES WW BB BB YES WWWBWWB BWWBBWW NO NO YES WWB BWW BBB BWW WWB YES WWBWWWWWW WWBBWWWBB WBBWWBWWW WWWWBBWBB BWWBBWWWW BWWWWWBWB BWWWBWWWW YES WBWWWWW BBBWWWB BWWWWWW BBWWWWB WBBBWWB WWBBWBB WWWBWWB WWWWWWB BWWWBWW YES WW BB W...
result:
ok ok (10000 test cases)
Test #4:
score: 0
Accepted
time: 502ms
memory: 3740kb
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 BBBBBBW WBWBBBB WBBBBWB WWWBBWB BBWBBBB BBWBWWB BWWBBBB YES WWWWWW WBWWBW WWWWWW WWWWWW WWWWWW WBWBWB WWWWWB WWWWWW WWWBBW WWBBWW YES BBWWWB BBWWBB YES WWBWBBWB YES WB WB BB BB BW YES WWBBB BWWBW WWWWW WWWWB WBWWW WWWBB WBWWB NO YES WWWW WBBB WBBW WBWW WWWB BWWW WWWB WWWB WWWW BBWB YES BWWBBB BB...
result:
ok ok (10000 test cases)
Test #5:
score: -100
Wrong Answer
time: 500ms
memory: 3736kb
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 W YES WWWBWBBWB BWBBWBWWW BBBBWBWBB WWWWWWWWB WWWBBBWWW BBWWWWWWW BBWWWWWWB YES WWBBBBW BWBWWWW BWBBBBW YES BBBWWB YES W W W B W W B NO NO YES WBBWBBW NO YES WBB WWB BBB BWB BWW BWB BBB NO YES BBB BWB WWW BBB WBW WWW BBB BBB BBB BWB YES WW BB BB WW WB BB WB NO YES BB BB BW BB BB WB BB BB NO YES ...
result:
wrong answer ans finds the answer, but out doesn't (test case 6550)