题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=4127

题目意思：

给n*n的方格，每个格子有一种颜色（0~5），每次可以选择一种颜色，使得和左上角相连（颜色相同以及相邻，间接也行）的所有的格子都为该颜色。求最少的步数，使得所有的方格颜色都相同。

解题思路：

bfs+bfs死活不给过。

正确解法应该是ID(dfs+bfs).因为总共的解的步数不多。

减枝：

1、当剩余的颜色种数（至少还要这么多步）+已走的步数>设定深度时 跳出。

2、注意每次搜的时候保证比前面的方格数多。

PS：时间卡的紧，不用STL，用手写队列。

代码：

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<string>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<stack>

#include<list>

#include<queue>

#include<ctime>

#define eps 1e-6

#define INF 0x3f3f3f3f

#define PI acos(-1.0)

#define ll __int64

#define lson l,m,(rt<<1)

#define rson m+1,r,(rt<<1)|1

#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

#define Maxn 10

int sa[Maxn][Maxn],n,ans,dep;

int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};

bool flag;

struct Po

{

    int x,y;

}q[80];

struct Inf

{

    int cnt;

    Po pp[70];

}; //存储一个连通块内的所有节点

bool vis[Maxn][Maxn];

bool iscan(int x,int y) //判断是否越界

{

    if(x<=0||x>n||y<=0||y>n)

        return false;

    return true;

}

void bfs(Inf & s,int co[])

{

    memset(vis,false,sizeof(vis));

    //queue<Inf>myq;

    s.cnt=0;

    Po tmp;

    tmp.x=1,tmp.y=1;

    s.pp[++s.cnt]=tmp;

    vis[1][1]=true;

    //myq.push(s);

    int head=0,tail=-1;

    q[++tail]=tmp;

    while(head<=tail)

    {

        //Inf cur=myq.front();

        //myq.pop();

        Po cur=q[head];

        ++head;

        int xx=cur.x,yy=cur.y;

        for(int i=0;i<4;i++)

        {

            int x=xx+dir[i][0],y=yy+dir[i][1];

            if(!iscan(x,y)||vis[x][y]||sa[x][y]!=sa[xx][yy])

                continue;

            vis[x][y]=true;

            Po tt;

            tt.x=x,tt.y=y;

            s.pp[++s.cnt]=tt;

            //myq.push(s);

            q[++tail]=tt;

        }

    }

    for(int i=1;i<=n;i++) //统计还没有进入连通块内的颜色种数

        for(int j=1;j<=n;j++)

        {

            if(!vis[i][j])

                co[sa[i][j]]++;

        }

}

void dfs(int co,int step,int num) //当前颜色，已走步数，已联通的方格个数

{

    if(step>dep||flag)

        return ;

    int cc[6]={0};

    Inf tmp;

    bfs(tmp,cc);

    if(tmp.cnt<=num)//往多的方格搜，不然浪费步数

        return ;

    num=tmp.cnt;

    //printf(":%d\n",num);

    //system("pause");

    if(num==n*n) //找到了

    {

        flag=true;

        ans=step;

        return ;

    }

    int nn=0;

    for(int i=0;i<6;i++)

        if(cc[i])

            nn++;

    if(nn+step>dep) //至少要这么多步

        return ;

    for(int i=0;i<6;i++)

    {

        if(i==co)

            continue;

        for(int j=1;j<=tmp.cnt;j++)

            sa[tmp.pp[j].x][tmp.pp[j].y]=i;

        dfs(i,step+1,num);

        for(int j=1;j<=tmp.cnt;j++) //回溯

            sa[tmp.pp[j].x][tmp.pp[j].y]=co;

    }

}

void IDA()

{

    flag=false;

    dep=1;

    while(!flag) //迭代加深搜索

    {

        dfs(sa[1][1],0,0);

        ++dep;

    }

}

int main()

{

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

    {

        for(int i=1;i<=n;i++)

            for(int j=1;j<=n;j++)

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

        IDA();

        printf("%d\n",ans);

    }

   return 0;

}