QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#273223#5070. Check Pattern is Badsio_TL 3745ms3620kbC++144.7kb2023-12-02 22:10:322023-12-02 22:10:33

Judging History

你现在查看的是最新测评结果

  • [2023-12-02 22:10:33]
  • 评测
  • 测评结果:TL
  • 用时:3745ms
  • 内存:3620kb
  • [2023-12-02 22:10:32]
  • 提交

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
...

result: