QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#492013 | #5070. Check Pattern is Bad | TheRaptor | TL | 0ms | 3616kb | C++14 | 2.5kb | 2024-07-26 07:58:36 | 2024-07-26 07:58:36 |
Judging History
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 ...