QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#519438#5070. Check Pattern is BadzhouhuanyiWA 28ms3936kbC++142.6kb2024-08-14 20:14:582024-08-14 20:14:58

Judging History

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

  • [2024-08-14 20:14:58]
  • 评测
  • 测评结果:WA
  • 用时:28ms
  • 内存:3936kb
  • [2024-08-14 20:14:58]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<random>
#include<cassert>
#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=length=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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3936kb

input:

3
2 2
??
??
3 3
BW?
W?B
?BW
3 3
BW?
W?W
?W?

output:

YES
BB
WB
NO
YES
BWB
WWW
BWB

result:

ok ok (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 28ms
memory: 3752kb

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
WB
BB
BW
WW
WW
NO
NO
YES
B
W
W
B
B
W
W
W
B
B
YES
WBWW
WWWB
WWWB
WWWW
BWWB
WWWW
WWWB
BWWW
BWBW
WWBW
YES
WBW
WWW
WBB
WWB
WWW
WWW
BBB
BWW
YES
W
B
B
B
YES
WBWB
WWWB
YES
BWWBBB
BBWWWB
YES
WBWWB
YES
BWBBWW
WWBBBB
BBBWBW
WBWWBW
YES
W
YES
BWB
BBB
WBB
WBB
WWB
BBB
BWW
BWW...

result:

wrong answer There is a check pattern in (1, 5) (test case 548)