今天做的福州賽區區域賽的題目重現，一整場都在摳這道題仍然無法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; } ~~~