题目链接：水叮当的舞步
我现在开始发题目链接了(主要还是因为懒得整理题面)……
这道题一开始是看到MashiroSky在写，于是我也开始写这道题了(说白了就是狙击他)……
这道题看到这么小的范围当然给人的第一感觉就是搜索了。于是我果断写了个搜索，后果很惨……我都没敢交上去……
后来想了各种优化，一路优化到了$80$分。最后的我想不出来了，于是就去翻了题解，终于弄全了。
首先，这道题最好使用迭代加深搜索。因为普通的$dfs$太慢，而$bfs$空间又开不下(听说某位大神使用$bfs$切掉了)。
接下来就是各种剪枝。每次都要对左上角的联通块进行拓展，这一步很耗时间。于是我们可以考虑给每个格子染上色，已经在左上角联通块内的染为$1$，在边上的染为$2$，其余的就是$3$了。于是每次拓展的时候我们只需可以找出所有颜色为$2$(是我们自己染上的颜色)的格子进行拓展即可。
然后我们可以对当前状态进行估价。设联通块外的颜色(输入的颜色)数为$x$，那么至少需要$x$步才可以让剩下的格子颜色相同。减掉一批。
另外还剩下一个，那就是当改变颜色后左上角联通块大小没有改变，那么这一步染色是无效的，可以直接减掉。
大概就是这些了。这道题用到了估价函数，那么就是$A*$搜索？
下面贴代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define N 9 using namespace std; int a[N][N],n,now;//a数组是输入的颜色,co数组是我自己染的颜色
int co[N][N],ans,yan[6],sheng;//yan数组标记剩下的每种颜色的数目,sheng就是剩余的不同种类颜色数
int zx[4]={1,-1,0,0},zy[4]={0,0,1,-1}; void color(int x,int y){//将(x,y)所在联通块纳入左上角联通块
if(!(--yan[a[x][y]])) sheng--;
co[x][y]=1; now++;
for(int k=0,i,j;k<4;k++){
i=x+zx[k],j=y+zy[k];
if(i>=1 && i<=n && j>=1 && j<=n && co[i][j]!=1){
if(a[i][j]==a[x][y]) color(i,j);
else co[i][j]=2;
}
}
} bool pd(int x){//判断联通块大小是否改变，顺便进行染色
bool ww=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(co[i][j]==2 && a[i][j]==x)
color(i,j),ww=1;
return ww;
} bool dfs(int d){
if(sheng>d) return 0;
if(now==n*n) return 1;
if(!d) return 0;
int zan[N][N],col[6],nn=now,ns=sheng;
for(int i=0;i<6;i++){
memcpy(zan,co,sizeof(co));
memcpy(col,yan,sizeof(yan));
if(pd(i)){
if(dfs(d-1)) return 1;
memcpy(co,zan,sizeof(co));
memcpy(yan,col,sizeof(yan));
now=nn;sheng=ns;
}
}
return 0;
} int main(){
File("a");
while(scanf("%d",&n)==1 && n){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
scanf("%d",&a[i][j]);
co[i][j]=3;
}
now=sheng=0; color(1,1); yan[a[1][1]]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(co[i][j]!=1) if(!(yan[a[i][j]]++)) sheng++;
for(ans=0;;ans++)
if(dfs(ans)){
printf("%d\n",ans);
break;
}
}
return 0;
}