HDU 4127 Flood-it! (IDA*+BFS) - c++编程基础

题意：给你一个n*n的格子，每个格子里面有一个数字（0到5），问你每次可以改变与(1，1)相连的相同数字变成任意其他数字，问你最少多少步能全部变成同一个数字。

题解：因为数据量有点大，宽搜会爆，深搜不知道尽头，所以用IDA*（迭代加深），BFS搜索与（1，1）相同的数字。

注意点细节就OK了。

AC代码：

#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
using namespace std;  
  
#define si1(a) scanf("%d",&a)  
#define si2(a,b) scanf("%d%d",&a,&b)  
#define sd1(a) scanf("%lf",&a)  
#define sd2(a,b) scanf("%lf%lf",&a,&b)  
#define ss1(s)  scanf("%s",s)  
#define pi1(a)    printf("%d\n",a)  
#define pi2(a,b)  printf("%d %d\n",a,b)  
#define mset(a,b)   memset(a,b,sizeof(a))  
#define forb(i,a,b)   for(int i=a;i




n||ty<1||ty>n||vis[tx][ty]||mp[tx][ty]!=mp[nx][ny]) continue ;  
            cur.x=tx;  
            cur.y=ty;  
            vis[tx][ty]=1;  
            q[++tail]=cur;  
        }  
    }  
    for(i=1;i<=n;i++)    // 标记还剩几种颜色  
    {  
        for(j=1;j<=n;j++)  
        {  
            if(!vis[i][j]) color[mp[i][j]]=1;  
        }  
    }  
}  
  
void dfs(int c,int cnt,int step)   // 当前颜色 连通块大小 步数  
{  
    if(step>depth||flag) return ;  // 已经搜到结果或当前步数大于已经得到的最小步数就return  
    int i,j,t=0,num,color[6]={0};  
    node tt;  
    bfs(tt,color);  
    num=tt.num;  
    if(num<=cnt) return ;      // 保证每次都要向变多的方向搜索  
    for(i=0;i<6;i++)           // 计算还剩几种颜色  
    {  
        t+=color[i];  
    }  
    if(step+t>depth) return ;  // 当前步数+还剩颜色数>depth return  
    if(num==n*n)  
    {  
        flag=1;  
        ans=step;  
        return ;  
    }  
    for(i=0;i<6;i++)  
    {  
        if(i==c) continue ;  
        for(j=1;j<=num;j++)   // 改变颜色  
        {  
            mp[tt.xx[j].x][tt.xx[j].y]=i;  
        }  
        dfs(i,num,step+1);  
        for(j=1;j<=num;j++)   // 还原颜色  
        {  
            mp[tt.xx[j].x][tt.xx[j].y]=c;  
        }  
    }  
}  
  
void IDA()  
{  
    int i,j;  
    flag=0;  
    depth=1;  
    while(!flag)  
    {  
        dfs(mp[1][1],0,0);  
        depth++;  
    }  
}  
  
int main()  
{  
    int i,j;  
    while(scanf("%d",&n),n)  
    {  
        for(i=1;i<=n;i++)  
        {  
            for(j=1;j<=n;j++)  
            {  
                scanf("%d",&mp[i][j]);  
            }  
        }  
        ans=INF;  
        IDA();  
        printf("%d\n",ans);  
    }  
    return 0;  
}  
/* 
4 
1 0 2 0 
1 2 0 3 
2 0 3 4 
5 1 1 4 
3 
0 1 2 
1 1 2 
2 2 1 
0 
*/