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

這個題是不是不能用BFS做呀？

#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;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(){freopen("Cola.txt","r",stdin);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); } 50分 DFS 超時

?

轉載于:https://www.cnblogs.com/thmyl/p/7206275.html

總結

以上是生活随笔為你收集整理的Codevs 1049 棋盘染色的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。