首页 > 代码库 > Codevs 1049 棋盘染色
Codevs 1049 棋盘染色
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
这题真JB蛋疼
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int ans=0x7fffffff;bool vis[10][10],color[10][10],now[10][10];int e[4][2]={{0,1},{0,-1},{1,0},{-1,0}};bool V[10][10];int cnt,fr,num;struct node{ int u,v;}point[30];bool check(int nx,int ny){ V[nx][ny]=1;cnt++; for(int i=0;i<4;i++){ int x=nx+e[i][0],y=ny+e[i][1]; if(x<=5&&x>=1&&y<=5&&y>=1){ if(now[x][y]&&!V[x][y]) check(x,y); } }}void dfs(int step){ if(step>ans)return; if(step>7)return; memset(V,0,sizeof(V)); cnt=0; int nx=0,ny=0;//找一个黑格子 for(int i=1;i<=5;i++){ for(int j=1;j<=5;j++) if(now[i][j]==1){ nx=i,ny=j; break; } if(nx&&ny)break; } check(nx,ny); if(cnt==step+fr)ans=min(ans,step); for(int i=1;i<=num;i++){ int x=point[i].u,y=point[i].v; if(!now[x][y]){ now[x][y]=1; dfs(step+1); now[x][y]=0; } }}char ch[10];int main(){ for(int i=1;i<=5;i++){ scanf("%s",ch+1); for(int j=1;j<=5;j++){ color[i][j]=ch[j]-‘0‘; now[i][j]=color[i][j]; if(color[i][j])fr++; if(!color[i][j]){ point[++num].u=i; point[num].v=j; } } } dfs(0); printf("%d",ans);}
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int map[10][10],copy[10][10],stan,First,cnt;bool ans,vis[10][10];char ch[10];int e[4][2]={{0,1},{0,-1},{-1,0},{1,0}};void check(int x,int y){ vis[x][y]=1; cnt++; for(int i=0;i<4;i++){ int xx=x+e[i][0],yy=y+e[i][1]; if(xx<=5&&xx>=1&&yy<=5&&yy>=1&&!vis[xx][yy]&&map[xx][yy]) check(xx,yy); }}void dfs(int x,int y,int k){ if(k==stan){ int xx=0,yy=0,now=0; for(int i=1;i<=5;i++){ for(int j=1;j<=5;j++){ if(map[i][j]){ xx=i;yy=j; now++; } } } cnt=0; memset(vis,0,sizeof(vis)); check(xx,yy); if(cnt==now){ ans=1; return; } } if(ans||x==6)return; for(int i=y;i<=5;i++){ if(map[x][i])continue; map[x][i]=1; dfs(x,i,k+1); map[x][i]=0; } for(int i=x+1;i<=5;i++){ for(int j=1;j<=5;j++){ if(map[i][j])continue; map[i][j]=1; dfs(i,j,k+1); map[i][j]=0; } }}int main(){ for(int i=1;i<=5;i++){ scanf("%s",ch+1); for(int j=1;j<=5;j++){ map[i][j]=ch[j]-‘0‘; } } for(stan=0;stan<=25;stan++){ dfs(1,1,0); if(ans==1){ printf("%d",stan); return 0; } }}
Codevs 1049 棋盘染色
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。