今天做的福州赛区区域赛的题目重现，一整场都在抠这道题仍然无法AC，时间卡的很紧，不过其实也是自己的搜索学的实在太差，紫书上刷的最少的就是第七章的题 。 我一开始就看出了这道题需要IDA*算法，但是昨天才看的还没能深入理解，通过赛后补这道题，感觉整体思路有了一个新的突破 。 IDA*算法就是迭代加深搜索和A*算法的结合，迭代加深搜索非常简单，就是从小到大枚举深度上限，适合求解深度未知的或者像该题一样需要求最小迭代次数的题目 。 A算法的精髓是写一个估价函数， 如何写呢？ 其实就是一个剪枝，通过计算预估一个比较松的下界，也就是预估从当前到达目标至少还要递归多少层，如果它加上当前深度d大于最大深度maxd，应当剪枝 。 事实上，IDA*算法的剪枝函数一般格式也都是这样的 ： d + h() > maxd 时剪枝 。有时候也不必严格的在代码里写出h()函数，只是要想清楚在什么情况下不可能在当前深度限制下出解即可 。 另一个非常重要的问题是如何对递归程序进行优化 。其实在场上我已经写出了估价函数，但是仍然超时 ，其原因就是我递归的太多了 。大家都知道如果扩展一颗完整的解答树，那么时间复杂度将极其可怕 ，而我写的暴力程序如果去掉估价函数，就是一颗完整的解答树 。 事实上我做了很多无用的递归 ，  大家可以想象一棵树，如果在第一开始就递归一个无用的分支，那么将会对造成极大的浪费 。 我是在每一层枚举6种颜色，都染上看看结果，其实答案只可能是染和当前连通块相邻的颜色（当前连通块就是和左上角元素相连的相同颜色的块）。 所以我们不妨在每一层里加个循环来找与之相邻的颜色，只递归他们 。 看似我们在每一层多加了个循环，浪费了时间，可是和次方级的解答树相比可以忽略不计了~因为我们剪掉了很多树枝 。 这给了我们大家一个启示： 宁可在每一层递归中多跑两个循环，也要想办法减少无用的递归 ！ 大家可以刷刷紫书上的埃及分数和编辑书稿 ，都很经典 。当然，我的第七章是刷的最少的，也是时候该补补了~ 细节见代码： ~~~ #include<bits/stdc++.h> using namespace std; const int maxn = 15; int n,maxd,a[maxn][maxn]; int vis[maxn][maxn]; int dx[] = { 0,1,0,-1,1,-1,-1,1 }; int dy[] = { 1,0,-1,0,1,-1,1,-1 }; void dfs2(int r,int c,int col) { //更新vis[i][j]数组，给vis[i][j] == 2的变成1，与之相邻的变成2 vis[r][c] = 1; for(int i=0;i<4;++i) { int x = r+dx[i]; int y = c+dy[i]; if(x < 0 || x >=n || y < 0 || y >= n ) continue; if(vis[x][y] == 1 ) continue; vis[x][y] = 2; if(a[x][y] == col) dfs2(x,y,col); } } int H() { int maze[8],cnt = 0; memset(maze,0,sizeof(maze)); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(vis[i][j]==1) continue; if(!maze[a[i][j]]) { maze[a[i][j]]++; cnt++; } } } return cnt; } int filled(int col) { int cnt = 0; for(int i=0;i<n;i++) for(int j=0;j<n;j++){ if(a[i][j] != col) continue; if(vis[i][j] == 2) { //只有当vis[i][j] == 2且与col同色的才染色 cnt++; dfs2(i,j,col); } } return cnt;//返回染色的个数 } bool dfs(int d) { if(d == maxd) return H()==0; if( ( H() + d ) > maxd ) return false; int vi[maxn][maxn]; memcpy(vi,vis,sizeof(vi)); for(int i=0;i<6;i++) { if(filled(i) == 0) continue; //没有符合要求的i颜色的块与之相邻 if(dfs(d+1)) return true; memcpy(vis,vi,sizeof(vis)); } return false; } int main() { while(~scanf("%d",&n)&&n) { for(int i=0;i<n;++i) for(int j=0;j<n;++j) scanf("%d",&a[i][j]); memset(vis,0,sizeof(vis)); dfs2(0,0,a[0][0]); for(maxd = 0; ; ++maxd) if(dfs(0)) break; printf("%d\n",maxd); } return 0; } ~~~