QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#519428 | #5070. Check Pattern is Bad | zhouhuanyi | WA | 36ms | 3748kb | C++14 | 2.6kb | 2024-08-14 20:10:26 | 2024-08-14 20:10:26 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<random>
#define N 100
using namespace std;
mt19937 RAND(random_device{}());
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
struct reads
{
int x,y;
};
reads tong[N*N+1];
int T,n,m,length;
char c[N+1][N+1];
bool op;
void solve(int x,int y,int opt)
{
if (op) return;
int sx,sy;
if ((c[x][y]=='B')+(c[x+1][y]=='W')+(c[x][y+1]=='W')+(c[x+1][y+1]=='B')==4)
{
op=1;
return;
}
if ((c[x][y]=='W')+(c[x+1][y]=='B')+(c[x][y+1]=='B')+(c[x+1][y+1]=='W')==4)
{
op=1;
return;
}
if ((c[x][y]=='B')+(c[x+1][y]=='W')+(c[x][y+1]=='W')+(c[x+1][y+1]=='B')==3)
{
if (c[x][y]=='?') c[x][y]='W',sx=x,sy=y;
else if (c[x+1][y]=='?') c[x+1][y]='B',sx=x+1,sy=y;
else if (c[x][y+1]=='?') c[x][y+1]='B',sx=x,sy=y+1;
else if (c[x+1][y+1]=='?') c[x+1][y+1]='W',sx=x+1,sy=y+1;
else return;
if (opt) tong[++length]=(reads){sx,sy};
if (sx!=1&&sy!=n) solve(sx-1,sy,opt);
if (sx!=n&&sy!=1) solve(sx,sy-1,opt);
if (sx!=1&&sy!=1) solve(sx-1,sy-1,opt);
}
if ((c[x][y]=='W')+(c[x+1][y]=='B')+(c[x][y+1]=='B')+(c[x+1][y+1]=='W')==3)
{
if (c[x][y]=='?') c[x][y]='B',sx=x,sy=y;
else if (c[x+1][y]=='?') c[x+1][y]='W',sx=x+1,sy=y;
else if (c[x][y+1]=='?') c[x][y+1]='W',sx=x,sy=y+1;
else if (c[x+1][y+1]=='?') c[x+1][y+1]='B',sx=x+1,sy=y+1;
else return;
if (opt) tong[++length]=(reads){sx,sy};
if (sx!=1&&sy!=n) solve(sx-1,sy,opt);
if (sx!=n&&sy!=1) solve(sx,sy-1,opt);
if (sx!=1&&sy!=1) solve(sx-1,sy-1,opt);
}
return;
}
int main()
{
char cs;
T=read();
while (T--)
{
n=read(),m=read(),op=0;
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
cin>>c[i][j];
for (int i=1;i<=n-1;++i)
for (int j=1;j<=m-1;++j)
solve(i,j,0);
if (op) puts("NO");
else
{
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
if (c[i][j]=='?')
{
cs=(RAND()&1)?'W':'B',c[i][j]=cs,length=0;
if (i!=n&&j!=m) solve(i,j,1);
if (i!=1&&j!=m) solve(i-1,j,1);
if (i!=n&&j!=1) solve(i,j-1,1);
if (i!=1&&j!=1) solve(i-1,j-1,1);
if (op)
{
op=0;
for (int k=1;k<=length;++k) c[tong[k].x][tong[k].y]='?';
c[i][j]=cs^'W'^'B';
if (i!=n&&j!=m) solve(i,j,1);
if (i!=1&&j!=m) solve(i-1,j,1);
if (i!=n&&j!=1) solve(i,j-1,1);
if (i!=1&&j!=1) solve(i-1,j-1,1);
}
}
puts("YES");
for (int i=1;i<=n;++i)
{
for (int j=1;j<=m;++j) printf("%c",c[i][j]);
puts("");
}
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3748kb
input:
3 2 2 ?? ?? 3 3 BW? W?B ?BW 3 3 BW? W?W ?W?
output:
YES WW WW NO YES BWW WWW BWB
result:
ok ok (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 36ms
memory: 3728kb
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 BB WB BB YES WB WB BB BW WW BB NO NO YES B W W B B W W W B B YES BBWW WWWB WWWB BWWW BWBB WWWW WBWW WWWW BBBW WBWW YES WBW WBB WBB WBW WBW WBW WWW WWB YES W B B W YES BBWB WWWB YES BBWBBB BWWWWB YES WWWWB YES BWBBWB WWBWWB BBBWWB WWWWWW YES W YES BWB BBB WBW WBB WWB WBB BBW WWW...
result:
wrong answer ans finds the answer, but out doesn't (test case 1504)