题目：http://poj.org/problem?id=4007

思路：

（lyd学长的思路）

IDA*算法，首先迭代加深限制搜索深度。

可以发现如果当前矩阵中除了左上角的连通块之外，共有M种颜色，那么还需要的步数不小于M。如果当前搜索深度+估价函数的值>深度限制，可以剪枝。

如果改变颜色后，左上角格子所在的联通块大小没有改变，可以剪枝，避免来回往复地搜索。

每次寻找左上角的格子所在的连通块耗费的时间常数巨大，可以在这里寻求突破。我们引入一个N*N的v数组。左上角的格子所在的连通块里的格子标记为1。左上角连通块周围一圈格子标记为2，其它格子标记为0。如果某次选择了颜色c，我们只需要找出标记为2并且颜色为c的格子，向四周扩展，并相应地修改v标记，就可以不断扩大标记为1的区域，最终如果所有格子标记都是1，就找到了答案。

//By SiriusRen

#include <cstdio>

#include <cstring>

using namespace std;

#define ff for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)

int n,a[10][10],vis[10][10],xx[]={1,-1,0,0},yy[]={0,0,1,-1},T;

bool check(int x,int y){return x>=1&&y>=1&&x<=n&&y<=n;}

void dye(int x,int y,int color){

    vis[x][y]=1;

    for(int i=0;i<=3;i++){

        int dx=x+xx[i],dy=y+yy[i];

        if(vis[dx][dy]==1||!check(dx,dy))continue;

        if(a[dx][dy]==color)dye(dx,dy,color);

        else vis[dx][dy]=2;

    }

}

int h(){

    int cnt=0,col[6];

    memset(col,0,sizeof(col));

    ff if(vis[i][j]!=1&&!col[a[i][j]])

        cnt++,col[a[i][j]]=1;

    return cnt;

}

bool count(int color){

    bool flag=0;

    ff if(a[i][j]==color&&vis[i][j]==2)

        flag=1,dye(i,j,color);

    return flag;

}

bool A_star(int deep){

    if(deep==T)return !h();

    if(deep+h()>T)return 0;

    for(int ii=0;ii<=5;ii++){

        int temp[9][9];

        ff temp[i][j]=vis[i][j];

        if(!count(ii))continue;

        if(A_star(deep+1))return 1;

        ff vis[i][j]=temp[i][j];

    }

    return 0;

}

int main(){

    while(~scanf("%d",&n)&&n){

        memset(vis,0,sizeof(vis));

        ff scanf("%d",&a[i][j]);

        dye(1,1,a[1][1]);

        for(T=h();;T++){

            if(A_star(0)){printf("%d\n",T);break;}

        }

    }

}

哈哈哈哈哈