题目描述 Description
有一个5×5的棋盘，上面有一些格子被染成了黑色，其他的格子都是白色，你的任务的对棋盘一些格子进行染色，使得所有的黑色格子能连成一块，并且你染色的格子数目要最少。读入一个初始棋盘的状态，输出最少需要对多少个格子进行染色，才能使得所有的黑色格子都连成一块。（注：连接是指上下左右四个方向，如果两个黑色格子只共有一个点，那么不算连接）
输入描述 Input Description
输入包括一个5×5的01矩阵，中间无空格，1表示格子已经被染成黑色。
输出描述 Output Description
输出最少需要对多少个格子进行染色
样例输入 Sample Input
11100
11000
10000
01111
11111
样例输出 Sample Output
1
枚举染色的格子数，如果当前染色的个数可以满足是黑色格子连成一片，即为最终答案。
在dfs里面我们需要搜索染色的位置，然后最终判断是否合格，合格条件：能够连成一片的格子的个数等于染色的个数+总黑格的个数
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 100
using namespace std;
char ch;
bool vis[N][N];
int a[N][N],cnt,tot,sx,sy,ans;
]={,,,-},yy[]={,-,,};
int pd(int x,int y)
{
tot++;vis[x][y]=true;
;i<;i++)
{
int fx=x+xx[i],fy=y+yy[i];
&&fy>&&fx<=&&fy<=&&a[fx][fy])
pd(fx,fy);
}
}
int dfs(int x,int y,int now)
{
if(!now)
{
tot=;
memset(vis,,sizeof(vis));
pd(sx,sy);
return (cnt+ans)==tot;
}
;fy<=;fy++)
{
if(a[x][fy]) continue;
a[x][fy]=true;
)) ;
a[x][fy]=false;
}
;fx<=;fx++)
;fy<=;fy++)
{
if(a[fx][fy]) continue;
a[fx][fy]=true;
)) ;
a[fx][fy]=false;
}
;
}
int main()
{
;i<=;i++)
{
;j<=;j++)
{
scanf("%c",&ch);
a[i][j]=ch-';
if(a[i][j]) sx=i,sy=j,cnt++;
}
) scanf("\n");
}
;;ans++)
{
,,ans))
{
printf("%d",ans);
;
}
}
}