我打暴力不对，于是就看看题解，，，，，，IDA*就是限制搜索深度而已，这句话给那些会A*但不知道IDA*是什么玩意的小朋友
看题解请点击这里
上方题解没看懂的看看这：把左上角的一团相同颜色的范围，那个范围周围的一圈，和剩余范围分别用c[i][j]赋值为1,2,0。然后做IDA*,限制搜索深度，估值函数h为c[i][j]不为1的范围中的不同颜色数目，意思是至少要多少次才能达到要求。ans不断迭代，如果g+h>ans则退出，如果c数组全为1则说明找到方案。感觉IDA*比A*编程难度简单好多，不用建堆，不过就是比较难想出迭代加深的方案。
my code如下:
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 int N,a[9][9],c[9][9],dx[4]={1,0,-1,0},dy[4]={0,1,0,-1},ans; 6 bool flag,vis[6]; 7 int astarh() 8 { 9 int i,j,t=0; memset(vis,0,sizeof(vis)); 10 for (i=1;i<=N;++i) for (j=1;j<=N;++j) 11 if ((c[i][j]!=1)&&(vis[a[i][j]]==0)) 12 {vis[a[i][j]]=1;t++;} return t; 13 } 14 void dfs(int x,int y) 15 { 16 int i,j,nowx,nowy; 17 c[x][y]=1; 18 for (i=0;i<4;++i) 19 { 20 nowx=x+dx[i]; nowy=y+dy[i]; 21 if ((nowx<1)||(nowx>N)||(nowy<1)||(nowy>N)||(c[nowx][nowy]==1)) continue; 22 c[nowx][nowy]=2; if (a[x][y]==a[nowx][nowy]) dfs(nowx,nowy); 23 } 24 } 25 bool can(int k) 26 { 27 int i,j; bool p=0; 28 for (i=1;i<=N;++i) for (j=1;j<=N;++j) 29 if ((c[i][j]==2)&&(a[i][j]==k)) 30 {p=1; dfs(i,j);} return p; 31 } 32 void work(int k) 33 { 34 int pd=astarh(); 35 if (k+pd>ans) return; 36 if (pd==0) {flag=1;return;} 37 int tm[9][9],i; 38 for (i=0;i<=5;++i) 39 { 40 memcpy(tm,c,sizeof(c)); 41 if (can(i)) work(k+1); 42 memcpy(c,tm,sizeof(c)); 43 } 44 } 45 int main() 46 { 47 int i,j; 48 scanf("%d",&N); 49 while (N) 50 { 51 for (i=1;i<=N;++i) for (j=1;j<=N;++j) scanf("%d",&a[i][j]); 52 memset(c,0,sizeof(c)); dfs(1,1); flag=0; 53 for (ans=0;ans<=N*N;++ans) 54 {work(0); if (flag) {printf("%d\n",ans);break;}} 55 scanf("%d",&N); 56 } 57 return 0; 58 }
原文：http://www.cnblogs.com/abclzr/p/5051748.html