【POJ】4007.Flood-it!

原题戳这里

题解

搜索是个好东西，不是人人都会搜

迭代加深，然后用一个函数估值，值是除了和左上连通的部分还有几个颜色不同的块，如果走的步数加上估值大于当前枚举的深度就跳出

代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <cstring>
#include <ctime>
#define MAXN 200005
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
int N,a[10][10],D,vis[10][10],_vis[10][10];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
void pre(int x,int y) {
	vis[x][y] = 1;
	for(int i = 0 ; i <= 3 ; ++i) {
		if(vis[x + dx[i]][y + dy[i]]) continue;
		if(a[x + dx[i]][y + dy[i]] == a[x][y]) {
			pre(x + dx[i],y + dy[i]);
		}
	}
}
bool expend(int x,int y,int c) {
	_vis[x][y] = 1;
	bool flag = 0;
	if(!vis[x][y]) flag = 1;
	for(int i = 0 ; i <= 3 ; ++i) {
		if(_vis[x + dx[i]][y + dy[i]]) continue;
		if(vis[x + dx[i]][y + dy[i]] || a[x + dx[i]][y + dy[i]] == c) 
			flag = expend(x + dx[i],y + dy[i],c) || flag;
	}
	return flag;
}
int calc() {
	bool used[6];memset(used,0,sizeof(used));
	for(int i = 1 ; i <= N ; ++i) {
		for(int j = 1 ; j <= N ; ++j) {
			if(!vis[i][j]) {
				used[a[i][j]] = 1;
			}
		} 
	}
	int res = 0;
	for(int i = 0 ; i <= 5 ; ++i) res += used[i];
	return res;
}
bool dfs(int dep) {
	if(dep > D) {
		if(calc() == 0) return 1;
		else return 0;
	}
	if(dep + calc() - 1 > D) return false;
	for(int i = 0 ; i <= 5 ; ++i) {
		memset(_vis,0,sizeof(_vis));
		if(!expend(1,1,i)) continue;
		int cpy[10][10];
		memcpy(cpy,vis,sizeof(vis));
		memcpy(vis,_vis,sizeof(vis));
		if(dfs(dep + 1)) return 1;
		memcpy(vis,cpy,sizeof(cpy));
	}
	return false;
}
void Solve() {
	bool used[6];
	memset(used,0,sizeof(used));
	for(int i = 1 ; i <= N ; ++i) {
		for(int j = 1 ; j <= N ; ++j) {
			scanf("%d",&a[i][j]);
			used[a[i][j]] = 1;
		}
	}
	for(int i = 0 ; i <= N + 1; ++i) {
		a[0][i] = a[N + 1][i] = 6;
		a[i][0] = a[i][N + 1] = 6;
	}
	memset(vis,0,sizeof(vis));
	pre(1,1);
	if(calc() == 0) {puts("0");return;}
	for(int dep = calc(); ; ++dep) {
		D = dep;
		if(dfs(1)) {
			printf("%d
",dep);
			return;
		} 
	}
}

int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    while(scanf("%d",&N)!=EOF && N) {
    	if(N == 0) break;
    	Solve();
    }
    return 0;
}