HDU 4127 Flood-it! (IDA*+BFS)
题意:给你一个n*n的格子,每个格子里面有一个数字(0到5),问你每次可以改变与(1,1)相连的相同数字 变成任意其他数字,问你最少多少步能全部变成同一个数字。题解:因为数据量有点大,宽搜会爆,深搜不知道尽头,所以用IDA*(迭代加深),BFS搜索与(1,1)相同的数字。
注意点细节就OK了。
AC代码:
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cstdlib> #include <cmath> #include <vector> #include <list> #include <deque> #include <queue> #include <iterator> #include <stack> #include <map> #include <set> #include <algorithm> #include <cctype> 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<b;i++) #define ford(i,a,b) for(int i=a;i<=b;i++) typedef __int64 LL; const int N=10; const int M=1000007; const int INF=0x3f3f3f3f; const double PI=acos(-1.0); const double eps=1e-7; int n,m,ans,flag,depth; int mp[N][N]; int dx[]={-1,1,0,0}; int dy[]={0,0,-1,1}; bool vis[N][N]; struct Node { int x,y; }cur,now,q[100]; struct node { int num; Node xx[100]; }; void bfs(node &tt,int color[]) { int i,j,nx,ny,tx,ty; int head=0,tail=-1; tt.num=0; memset(vis,0,sizeof(vis)); cur.x=cur.y=1; vis[1][1]=1; q[++tail]=cur; while(head<=tail) { now=q[head]; head++; tt.xx[++tt.num]=now; nx=now.x; ny=now.y; for(i=0;i<4;i++) { tx=nx+dx[i]; ty=ny+dy[i]; if(tx<1||tx>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 */
补充:软件开发 , C++ ,