题目描述 Description
有一个5×5的棋盘，上面有一些格子被染成了黑色，其他的格子都是白色，你的任务的对棋盘一些格子进行染色，使得所有的黑色格子能连成一块，并且你染色的格子数目要最少。读入一个初始棋盘的状态，输出最少需要对多少个格子进行染色，才能使得所有的黑色格子都连成一块。（注：连接是指上下左右四个方向，如果两个黑色格子只共有一个点，那么不算连接）
输入描述 Input Description
输入包括一个5×5的01矩阵，中间无空格，1表示格子已经被染成黑色。
输出描述 Output Description
输出最少需要对多少个格子进行染色
样例输入 Sample Input
11100
11000
10000
01111
11111
样例输出 Sample Output
1
题解
据说限制dfs深度的dfs是迭代深搜，我也不懂是不是，总觉得很厉害。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
char ch[10];
int map[10][10],t[6][6],ans;
int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};
void init()
{
int i,j;
for(i=1;i<=5;i++)
{scanf("%s",ch+1);
for(j=1;j<=5;j++)
map[i][j]=ch[j]-'0';
}
}
void del(int x,int y)
{
t[x][y]=0;
int i,tx,ty;
for(i=0;i<4;i++)
{tx=x+xx[i]; ty=y+yy[i];
if(tx<1||ty<1||tx>5||ty>5||!t[tx][ty]) continue;
del(tx,ty);
}
}
bool check()
{
int tag=0,i,j;
for(i=1;i<=5;i++)
for(j=1;j<=5;j++)
t[i][j]=map[i][j];
for(i=1;i<=5;i++)
for(j=1;j<=5;j++)
{if(t[i][j])
{if(tag==0)
{del(i,j); tag=1;}
else return false;
}
}
return true;
}
void dfs(int x,int y,int k,int maxk)
{
if(k==maxk)
{if(check()) ans=1;
return ;
}
if(ans||x==6) return;
int i,j;
for(i=y;i<=5;i++)
{if(map[x][i]) continue;
map[x][i]=1;
if(i==5) dfs(x+1,1,k+1,maxk);
else dfs(x,i+1,k+1,maxk);
map[x][i]=0;
}
for(i=x+1;i<=5;i++)
for(j=1;j<=5;j++)
{if(map[i][j]) continue;
map[i][j]=1;
if(j==5) dfs(i+1,1,k+1,maxk);
else dfs(i,j+1,k+1,maxk);
map[i][j]=0;
}
}
void work()
{
int i;
for(i=0;i<=25;i++)
{dfs(1,1,0,i);
if(ans) {printf("%d",i); return;}
}
}
int main()
{
init(); work();
return 0;
}