文章目录

• 前言
• 题目
• 做法

前言

这个算法很久没有遇到了…

题目

codevs-传送门

做法

IDA*，每次放宽 $Maxd$Maxd，可以用一个cnt记录每种数字的个数，则启发式函数$h$h可设置为当前还存在的不同数字个数。然后可将点分为3种：未选，已选，待选。
注意还原现场即可

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<climits>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define LL long long
#define ULL unsigned long long
using namespace std;
int read(){
	int f=1,x=0;char c=getchar();
	while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
	while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return f*x;
}
int Maxd,Map[10][10],vis[10][10];
int n,cnt[7],dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void Move(int x,int y,int col){
	vis[x][y]=1,cnt[Map[x][y]]--;
	for(int t=0;t<=3;t++){
		int nx=x+dir[t][0],ny=y+dir[t][1];
		if(nx<1||ny<1||nx>n||ny>n||vis[nx][ny]==1) 
			continue;
		if(Map[nx][ny]==col)
			Move(nx,ny,col);
		else vis[nx][ny]=2;
	}
	return ;
}
bool Add(int col){
	bool f=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(vis[i][j]==2&&Map[i][j]==col)
				f=1,Move(i,j,col);
	return f;
}
int h(){
	int ret=0;
	for(int i=0;i<=5;i++)
		ret+=(cnt[i]!=0);
	return ret;
}
bool DFS(int d){
	int t=h();
	if(!t) return 1;
	if(d+t>Maxd) return 0;
	int tmp[10][10],siz[7];
	for(int i=0;i<=5;i++){
		memcpy(siz,cnt,sizeof(cnt));
		memcpy(tmp,vis,sizeof(vis));
		if(Add(i)&&DFS(d+1))
			return 1;
		memcpy(cnt,siz,sizeof(cnt));
		memcpy(vis,tmp,sizeof(vis));
	}
	return 0;
}
int main(){
	while(1){
		n=read();
		if(!n) break;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				Map[i][j]=read(),cnt[Map[i][j]]++;
		Move(1,1,Map[1][1]);
		Maxd=0;
		while(!DFS(0))
			Maxd++;
		printf("%d\n",Maxd);
		memset(cnt,0,sizeof(cnt));
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			vis[i][j]=0;
	}
	return 0;
}