QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#274960 | #5070. Check Pattern is Bad | sio_ | WA | 521ms | 3788kb | C++14 | 3.4kb | 2023-12-04 09:03:33 | 2023-12-04 09:03:34 |
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: 1ms
memory: 3788kb
input:
3 2 2 ?? ?? 3 3 BW? W?B ?BW 3 3 BW? W?W ?W?
output:
YES BW BB NO YES BWW WWW WWB
result:
ok ok (3 test cases)
Test #2:
score: 0
Accepted
time: 521ms
memory: 3680kb
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 BB BB WB BB YES WB BB BW BW WW WB NO NO YES B W B B B W W W B B YES WWWW WBWW WWWB BWWW WWWB WWWW WWWW WWWW WBWW BBBW YES WBW WBW WBW BBB WBW WWW WBB WWW YES W B B B YES BBWB WWWB YES BBBBBB BBWBWB YES WBWWB YES BWWWWB WWBWBB BBBWWW WBWWBW YES B YES BWB BBB WBB WBB WWB BBB BBW WWW...
result:
ok ok (10000 test cases)
Test #3:
score: -100
Wrong Answer
time: 503ms
memory: 3736kb
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 W B B B W W B B W YES WWBB WWWB WBWB WWWB BBWW BBWB WWWW BBWB BWWW YES WW BB BB YES BWWBWWB BWWBWWW NO NO YES WWB BWB BBB BWW WWB YES WWBWWWBBB WWBBBWWBB WWBBBBWBW WWWWBWWWW WWBWWWBWW WWWWWWWWW BWWWBWBWB YES WBWWWWW BBBBWBW WWWWWWW BWWWWWB BBBBWWB WBWBWBB WWWWWWB WWWWWWB WWWBBWW YES WB BB B...
result:
wrong answer ans finds the answer, but out doesn't (test case 4429)