NKOJ 2440 数字消除游戏【迭代加深+剪枝】

问题描述

在一个n*n的方形棋盘上玩消除游戏，棋盘上布满了数字。
每一步，玩家可以任选一个数字x，用它填充坐标为(1,1)格子所在连通区域，该区域的数字都会变成x。（如果两个数字相同且相邻，我们称这两个数字连通。相邻是上下左右四方向）。
当整个棋盘的数字都相同时，就可以将整个棋盘上的数字消除掉，游戏结束。
问，最少需要几次操作就能消除所有数字。

输入格式

有若干组测试数据(不超过20组)，对于每组测试数据：
第一行，一个整数n，表示棋盘的尺寸。
接下来一个n*n的数字矩阵，表示游戏的初始局面。
当输入的n==0时，输入结束。

输出格式

对于每组测试数据，输出一行，一个整数，表示最少需要的操作数。

#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define rep(i,x,y) for(ll i=(x);i<=(y);i++)
#define repl(i,x,y) for(ll i=(x);i<(y);i++)
#define repd(i,x,y) for(ll i=(x);i>=(y);i--)
using namespace std;

const ll N=10;

ll n,tim,mp[N][N],vis[N][N];

ll dx[4]={0,0,-1,1};
ll dy[4]={-1,1,0,0};

map<ll,ll>Hash;

inline ll read() {
	ll x=0;char ch=getchar();bool f=0;
	while(ch>'9'||ch<'0'){if(ch=='-')f=1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return f?-x:x;
}

void dfs(ll x,ll y,ll z) {
	vis[x][y]=1;
	
	rep(i,0,3) {
		ll tx=x+dx[i],ty=y+dy[i];
		
		if(tx<1||ty<1||tx>n||ty>n||vis[tx][ty]==1) continue;
		
		vis[tx][ty]=2;
		
		if(mp[tx][ty]==z) dfs(tx,ty,z);
	}
}

ll getleft() {
	ll ret=0,col[7]={0};
	rep(i,1,n) rep(j,1,n) if(!col[mp[i][j]]&&vis[i][j]!=1) {
		col[mp[i][j]]=1;ret++;
	}return ret;
}

ll getfill(ll z) {
	ll ret=0;
	rep(i,1,n) rep(j,1,n) if(mp[i][j]==z&&vis[i][j]==2) {
		++ret;dfs(i,j,z);
	}return ret;
}

ll idastar(ll dep,ll lim) {
	ll ret=getleft();
	
	if(dep+ret>lim) return 0;
	
	if(!ret) return 1;
	
	ll vvis[N][N]={0};
	
	rep(i,1,tim) {
		memcpy(vvis,vis,sizeof(vis));
		if(getfill(i)&&idastar(dep+1,lim)) return 1;
		memcpy(vis,vvis,sizeof(vis));
	}
	
	return 0;
}

int main() {
	while(true) {
		n=read();
		
		if(!n) return 0;
		
		while(Hash.size()) Hash.erase(Hash.begin());
		
		tim=0;
		
		rep(i,1,n) rep(j,1,n) {
			mp[i][j]=read();
			if(!Hash[mp[i][j]]) Hash[mp[i][j]]++;mp[i][j]=Hash[mp[i][j]];
		}
		
		memset(vis,0,sizeof(vis));
		
		dfs(1,1,mp[1][1]);
		
		rep(dep,0,N*N) if(idastar(0,dep)) {
			printf("%lld\n",dep);break;
		}
	}

	return 0;
}