QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#492013#5070. Check Pattern is BadTheRaptorTL 0ms3616kbC++142.5kb2024-07-26 07:58:362024-07-26 07:58:36

Judging History

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

  • [2024-07-26 07:58:36]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3616kb
  • [2024-07-26 07:58:36]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int grid[105][105];
int n,m;
pair<int,int> check(int x, int y){
	int num=0;
	pair<int,int> ret={-1,-1};
	for(int i=0; i<2; i++) for(int j=0; j<2; j++){
		if(grid[x+i][y+j]==0){
			num++;
			ret={x+i,y+j};
		}
	}
	if(num!=1) return {-1,-1};
	if(grid[x][y]!=grid[x+1][y]&&grid[x][y]!=grid[x][y+1]){
		if(grid[x][y+1]!=grid[x+1][y+1]&&grid[x+1][y]!=grid[x+1][y+1]){
			return ret;
		}
	}
	return {-1,-1};
}
void dfs(int x, int y, int v){
	grid[x][y]=v;
	pair<int,int> yey=check(x-1,y-1);
	if(yey.first!=-1){
		if(yey.first<x) dfs(yey.first,yey.second,grid[yey.first+1][yey.second]);
		else dfs(yey.first,yey.second,grid[yey.first][yey.second+1]);
	}
	yey=check(x-1,y);
	if(yey.first!=-1){
		if(yey.first<x) dfs(yey.first,yey.second,grid[yey.first+1][yey.second]);
		else dfs(yey.first,yey.second,grid[yey.first][yey.second-1]);
	}
	yey=check(x,y-1);
	if(yey.first!=-1){
		if(yey.first>x) dfs(yey.first,yey.second,grid[yey.first-1][yey.second]);
		else dfs(yey.first,yey.second,grid[yey.first][yey.second+1]);
	}
	yey=check(x,y);
	if(yey.first!=-1){
		if(yey.first>x) dfs(yey.first,yey.second,grid[yey.first-1][yey.second]);
		else dfs(yey.first,yey.second,grid[yey.first][yey.second-1]);
	}
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
		cin >> n >> m;
		for(int i=1; i<=n; i++){
			for(int j=1; j<=m; j++){
				char c;
				cin >> c;
				if(c=='B') grid[i][j]=1;
				else if(c=='W') grid[i][j]=2;
				else grid[i][j]=0;
			}
		}
		for(int i=1; i<n; i++){
			for(int j=1; j<m; j++){
				pair<int,int> yey=check(i,j);
				if(yey.first!=-1){
					if(yey.first>i) dfs(yey.first,yey.second,grid[yey.first-1][yey.second]);
					else dfs(yey.first,yey.second,grid[yey.first][yey.second-1]);
				}
			}
		}
		for(int i=1; i<=n; i++){
			for(int j=1; j<=m; j++){
				if(grid[i][j]==0) dfs(i,j,1);
			}
		}
		bool can=true;
		for(int i=1; i<n; i++){
			for(int j=1; j<m; j++){
				if(grid[i][j]!=grid[i+1][j]&&grid[i][j]!=grid[i][j+1]){
					if(grid[i+1][j]!=grid[i+1][j+1]&&grid[i][j+1]!=grid[i+1][j+1]){
						can=false;
					}
				}
			}
		}
		cout << (can?"YES\n":"NO\n");
		if(can){
			for(int i=1; i<=n; i++){
				for(int j=1; j<=m; j++){
					if(grid[i][j]==1) cout << 'B';
					else cout << 'W';
				}
				cout << '\n';
			}
		}
		for(int i=1; i<=n; i++){
			for(int j=1; j<=m; j++) grid[i][j]=0;
		}
	}
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3616kb

input:

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

output:

YES
BB
BB
NO
YES
BWB
WWW
BWB

result:

ok ok (3 test cases)

Test #2:

score: -100
Time Limit Exceeded

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:


result: