【wikioi】1049 棋盘染色（迭代深搜）

http://www.wikioi.com/problem/1049/

这题我之前写没想到迭代加深，看了题解，然后学习了这种搜索（之前我写的某题也用过，，但是不懂专业名词囧。）

迭代加深搜索就是限制搜索深度，一旦有可行解立即跳出，优化了深搜一直搜下去的毛病。

（囧，这题搜索题写了我一下午，我搜索的确很弱啊！！！）

第一次写出来的版本我没有注意到，应该是从多个点拓展下去，而不是从某个点。

第二次写出来的版本的确从所有可行点拓展下去，但是样例都tle。。

第三次看了别人的标程发现直接向右和向拓展就行了囧0.0一行一行的拓展，而不用向上拓展了（因为已经拓展过啊囧）

。。。

果然我是蒟蒻。。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define for1(i,a,n) for(int i=(a);i<=(n);++i)
#define for2(i,a,n) for(int i=(a);i<(n);++i)
#define for3(i,a,n) for(int i=(a);i>=(n);--i)
#define for4(i,a,n) for(int i=(a);i>(n);--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define read(a) a=getnum()
#define print(a) printf("%d", a)
inline int getnum() { int ret=0; char c; int k=1; for(c=getchar(); c<'0' || c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0' && c<='9'; c=getchar()) ret=ret*10+c-'0'; return k*ret; }

int m[7][7], vis[7][7], vis2[7][7];
const int fx[4]={-1, 1, 0, 0}, fy[4]={0, 0, -1, 1};

int s, flag;

void dfs2(int x, int y) {
	vis[x][y]=1;
	int nx, ny;
	rep(i, 4) {
		nx=x+fx[i]; ny=y+fy[i];
		if(nx>0 && nx<6 && ny>0 && ny<6 && m[nx][ny] && !vis[nx][ny]) 
			dfs2(nx, ny);
	}
}

bool check() {
	int nx=0, ny=0, f=0;
	for1(i, 1, 5) {
		for1(j, 1, 5) if(m[i][j]) { nx=i, ny=j; f=1; break; }
		if(f) break;
	}
	if(!nx && !ny) return false;
	CC(vis, 0);
	dfs2(nx, ny);
	for1(i, 1, 5) for1(j, 1, 5) if(m[i][j] && !vis[i][j]) return false;
	return true;
}

void dfs(int x, int y, int k) {
	if(k==s) { /*for1(i, 1, 5) {for1(j, 1, 5) print(m[i][j]); puts(""); }*/if(check()) flag=1; return; }
	if(flag||x==6) return;
	for1(i, y, 5) if(!m[x][i]) {
		m[x][i]=1;
		i==5?dfs(x+1, 1, k+1):dfs(x, i+1, k+1);
		m[x][i]=0;
	}
	for1(i, x+1, 5) for1(j, 1, 5) if(!m[i][j]) {
		m[i][j]=1;
		j==5?dfs(i+1, 1, k+1):dfs(i, j+1, k+1);
		m[i][j]=0;
	}
}

int main() {
	char c;
	int ans=25;
	for1(i, 1, 5) for1(j, 1, 5) {
		for(c=getchar(); c<'0'||c>'9'; c=getchar());
		m[i][j]=c-'0';
	}
	for1(i, 1, 25) {
		s=i;
		dfs(1, 1, 0);
		if(flag) { ans=i; break; }
	}
	print(ans);
	return 0;
}

题目描述 Description

有一个5×5的棋盘，上面有一些格子被染成了黑色，其他的格子都是白色，你的任务的对棋盘一些格子进行染色，使得所有的黑色格子能连成一块，并且你染色的格子数目要最少。读入一个初始棋盘的状态，输出最少需要对多少个格子进行染色，才能使得所有的黑色格子都连成一块。（注：连接是指上下左右四个方向，如果两个黑色格子只共有一个点，那么不算连接）

输入描述 Input Description

输入包括一个5×5的01矩阵，中间无空格，1表示格子已经被染成黑色。

输出描述 Output Description

输出最少需要对多少个格子进行染色

样例输入 Sample Input

11100

11000

10000

01111

11111

样例输出 Sample Output