QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#772275 | #5070. Check Pattern is Bad | OIer_kzc# | WA | 29ms | 3664kb | C++20 | 2.6kb | 2024-11-22 18:11:51 | 2024-11-22 18:11:52 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define pa pair<int,int>
char s[105][105];
int n,m,ans=1;
set<pair<int,int>> q;
inline void check(int x,int y){
if(x<1||y<1||x>=n||y>=m||ans==0)return ;
int cnt0=0,cnt1=0;
for(int i=0;i<2;i++) for(int j=0;j<2;j++) {
cnt0+=(s[x+i][y+j]=='W');
cnt1+=(s[x+i][y+j]=='B');
}
if(cnt0==4||cnt1==4){
ans=0;
return ;
}
if(cnt0&&cnt1)return ;
if(cnt0==3){
for(int i=0;i<2;i++) for(int j=0;j<2;j++) if(s[x+i][y+j]=='?') {
s[x+i][y+j]='B';
q.erase(make_pair(i+x,y+j));
check(x+i-1,y+j);
check(x+i-1,y+j-1);
check(x+i,y+j-1);
}
return ;
}
if(cnt1==3){
for(int i=0;i<2;i++) for(int j=0;j<2;j++) if(s[x+i][y+j]=='?') {
s[x+i][y+j]='W';
q.erase(make_pair(i+x,y+j));
check(x+i-1,y+j);
check(x+i-1,y+j-1);
check(x+i,y+j-1);
}
return ;
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int t;cin>>t;
while(t--){
cin>>n>>m;
ans=1;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
cin>>s[i][j];
if(i+j&1){
if(s[i][j]=='B') s[i][j]='W';
else if(s[i][j]=='W') s[i][j]='B';
}
}
q.clear();
fo(i,1,n){
fo(j,1,m){
if(s[i][j]=='?'){
q.insert(make_pair(i,j));
}
}
}
fo(i,1,n-1){
fo(j,1,m-1)check(i,j);
}
while(!q.empty()&&ans){
pair<int,int> u=*(q.begin());
int x=u.first,y=u.second;
q.erase(u);
s[x][y]='W';
check(x,y);
check(x-1,y);
check(x-1,y-1);
check(x,y-1);
}
fo(i,1,n-1){
fo(j,1,m-1){
if(!ans)break;
check(i,j);
}
}
if(ans){
cout<<"YES\n";
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i+j&1){
if(s[i][j]=='B') s[i][j]='W';
else if(s[i][j]=='W') s[i][j]='B';
}
cout<<s[i][j];
}
cout<<endl;
}
}
else cout<<"NO\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3664kb
input:
3 2 2 ?? ?? 3 3 BW? W?B ?BW 3 3 BW? W?W ?W?
output:
YES WB BB NO YES BWW WWW WWW
result:
ok ok (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 29ms
memory: 3656kb
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 WW BB YES WB BB BB BW WW BW NO NO YES B W W B B W W W B B YES WBWW WWWW WWWB BWWW WWWB BWWW WWWB BWWW WWWW BWBW YES WBW WWW WBW BBB WBW WWW WBW WWW YES W B W B YES WBWB WWWB YES BBWBBB BWWWWB YES WBWBW YES BWWBWB WWBBBB BBBWWB WWWWWW YES W YES BWB BBB WBW BBB WWB BBB BBW BWW...
result:
wrong answer ans finds the answer, but out doesn't (test case 548)