C. C. Blog

Security Research, Algorithm and Data Structure

51Nod 1388 六边形平面

Problem

现在有一个NN的六边形网格平面(这种平面类似蜂窝形状)。下图是N=1,2,3,4条件下的具体形状,根据它们可以依次类推N=5,6,....。 现在你需要对NN网格中一些格子进行上色,在给定的输入中这些格子被标记上字符‘X’,而不用上色的网格被标记为‘-’。上色时需要注意,如果两个被上色的格子有公共边,那么这两个格子需要被涂成不同的颜色。问最少需要多少种颜色来完成任务?

Solution

结论,最多三种颜色,判断一种两种行不行即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<stdio.h>
#include<cstring>
#include<iostream>
using namespace std;
int T,n;
int a[120][120];
int col[120][120];
int ck1(int x,int y){
return x-1>0&&a[x-1][y];
}
int ck2(int x,int y){
return x-1>0&&y+1<=n&&a[x-1][y+1];
}
int ck3(int x,int y){
return y-1>0&&a[x][y-1];
}
int t=0;
int f[10][10]={{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0}};
bool check(int x,int y){
for(int i=0;i<6;i++){
int xx=x+f[i][0],yy=y+f[i][1];
if(xx<1||yy<1||xx>n||yy>n||!a[xx][yy]) continue;
if(col[x][y]==col[xx][yy]) return false;
}
return true;
}
void dfs(int x,int y,int c){
if(t) return;
col[x][y]=c;
if(!check(x,y)){
t=1;
return;
}
for(int i=0;i<6;i++){
int xx=x+f[i][0],yy=y+f[i][1];
if(xx<1||yy<1||xx>n||yy>n||col[xx][yy]||!a[xx][yy]) continue;
dfs(x+f[i][0],y+f[i][1],c^3);
}
}
int main(){
scanf("%d",&T);
while(T--){
t=0;
memset(col,0,sizeof(col));
scanf("%d",&n);
char s[60];
int fg=0;
for(int i=1;i<=n;i++){
scanf("%s",s);
for(int j=1;j<=n;j++){
if(s[j-1]=='X'){
a[i][j]=1;
fg=1;
}
else a[i][j]=0;
}
}
if(!fg){
printf("0\n");
continue;
}
fg=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][j]==0) continue;
int cur=ck1(i,j)|ck2(i,j)|ck3(i,j);
if(cur>0) fg=0;
}
}
if(fg){
printf("1\n");
continue;
}

for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][j]&&!col[i][j]) dfs(i,j,1);
}
}
if(!t){
printf("2\n");
}
else{
printf("3\n");
}
}
return 0;
}
  • 本文作者: CCWUCMCTS
  • 本文链接: https://ccwucmcts.github.io/posts/59654/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!