首页 > 代码库 > [Codevs] 1014 棋盘染色
[Codevs] 1014 棋盘染色
1049 棋盘染色
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
有一个5×5的棋盘，上面有一些格子被染成了黑色，其他的格子都是白色，你的任务的对棋盘一些格子进行染色，使得所有的黑色格子能连成一块，并且你染色的格子数目要最少。读入一个初始棋盘的状态，输出最少需要对多少个格子进行染色，才能使得所有的黑色格子都连成一块。（注：连接是指上下左右四个方向，如果两个黑色格子只共有一个点，那么不算连接）
输入描述 Input Description
输入包括一个5×5的01矩阵，中间无空格，1表示格子已经被染成黑色。
输出描述 Output Description
输出最少需要对多少个格子进行染色
样例输入 Sample Input
11100
11000
10000
01111
11111
样例输出 Sample Output
1
分析 Analysis
思维级模版题= =。
判重：HASH蛤习
判断输出：DFS求联通块
主体：BFS
注意点：状态表示
主要还是数据范围小= =感谢出题人放我蒟蒻一马Orz
代码 Code
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<queue> 5 #define LL long long 6 using namespace std; 7 8 const int dir[4][2] = {{0,1},{1,0},{-1,0},{0,-1}}; 9 10 bool swi = true; 11 12 struct MAP{ 13 int map[7][7],step,remain; 14 15 MAP(){ 16 memset(map,0,sizeof(map)); 17 step = remain = 0; 18 } 19 }; 20 21 queue<MAP> q; 22 23 bool HASH[21473650]; 24 25 LL GETHASH(MAP now){ 26 LL code = 0; 27 for(int i = 1;i <= 5;i++){ 28 for(int j = 1;j <= 5;j++){ 29 code = (code<<1)+now.map[i][j]; 30 } 31 } 32 33 return code%21473648; 34 } 35 36 bool poicheck(int x,int y){ 37 if(x > 5 || x < 1 || y > 5 || y < 1) return false; 38 else return true; 39 } 40 41 int tot = 0; 42 bool chess[6][6]; 43 void dfs(int x,int y,MAP now){ 44 if(chess[x][y] || !now.map[x][y] || !poicheck(x,y)) return; 45 chess[x][y] = true; 46 tot++; 47 for(int i = 0;i < 4;i++){ 48 int nowx = x+dir[i][0]; 49 int nowy = y+dir[i][1]; 50 dfs(nowx,nowy,now); 51 } 52 } 53 54 bool check(MAP now){ 55 int x,y; 56 for(int i = 1;i <= 5;i++){ 57 for(int j = 1;j <= 5;j++){ 58 if(now.map[i][j]){ 59 x = i,y = j; 60 break; 61 } 62 } 63 } 64 65 memset(chess,false,sizeof(chess)); 66 tot = 0; 67 dfs(x,y,now); 68 69 if(tot == 25-now.remain) return true; 70 else return false; 71 } 72 73 void Input(){ 74 MAP tmp; 75 76 for(int i = 1;i <= 5;i++){ 77 for(int j = 1;j <= 5;j++){ 78 scanf("%1d",&tmp.map[i][j]); 79 if(!tmp.map[i][j]) tmp.remain++; 80 } 81 } 82 83 tmp.step = 0; 84 85 86 87 q.push(tmp); 88 } 89 90 void PUSH(MAP now){ 91 now.step++;now.remain--; 92 for(int i = 1;i <= 5;i++){ 93 for(int j = 1;j <= 5;j++){ 94 if(!now.map[i][j]){ 95 now.map[i][j] = 1; 96 97 LL code = GETHASH(now); 98 99 if(HASH[code]){100 now.map[i][j] = 0;101 continue;102 }else HASH[code] = 1;103 104 if(check(now)){105 printf("%d",now.step);106 swi = false;107 return;108 }109 q.push(now);110 now.map[i][j] = 0;111 }112 }113 }114 }115 116 void bfs(){117 while(!q.empty() && swi){118 MAP tmp = q.front();119 q.pop();120 // cout << ‘A‘;121 if(check(tmp)){122 printf("%d",tmp.step);123 swi = false;124 return;125 }126 127 PUSH(tmp);128 }129 }130 131 int main(){132 133 Input();134 bfs();135 136 return 0;137 }
[Codevs] 1014 棋盘染色
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。