這個問題是一個典型的類型的問題迷宮廣泛的搜索。

在網上看到了很多解決方案。

沒什么解決問題的分析報告，不指出其中的關鍵點。代碼更像是一大抄。一些分析師也有很大的文章分析。只是不要全部命中關鍵，什么是廣泛而深刻的，甚至搜索發現，在分析差異。為什么快速搜索寬像，什么樣的風暴喊搜索，都錯了。代碼都是抄過的。

通過一大段的時間研究，最終搞通了。

本題盡管能夠說是廣搜。可是當中的關鍵卻是剪枝法。為什么呢？

由于迷宮并不能簡單地廣搜就能搜索出全部路徑的，甚至僅僅要迷宮大點就不能搜索出是否有路徑。假設沒有條件剪枝的情況下。不信，你嚴格寫一個廣搜搜索一下迷宮路徑看看。當然你寫了個錯誤的廣搜。自然得出錯誤的答案了。

常見的錯誤是一格一格地擴展迷宮就以為是迷宮的廣搜了，錯！

真正的廣搜是須要把迷宮建圖。然后廣搜。

事實上真正的關鍵是剪枝：

剪枝思考就是要思考什么時候應該擴展到下一格？是否合法的格子就一定能夠擴展？當然不是，是須要依據題意剪枝。本題的題意是求用時最小的路徑。故此能夠由此想到應該是以時間比較來決定是否須要擴展到下一格的。

即下一格有可能找到更加優的解就擴展。否則就不擴展。

這樣一剪枝之后。就能夠使用所謂的廣搜了。

那么為什么本題。或者能夠說本題題型的題目不能夠使用深搜呢？

由于上面的剪枝條件是每一層去剪枝的，假設使用深搜，那么這種剪枝條件就無法用上了。

另一種做法就是利用優先隊列。優先擴展當前最小用時的格子。那么就能夠不用反復搜索下一格了。這也是利用了上面的剪枝思想。

只是僅僅要理解了上面的關鍵剪枝點，那么這種題目都能夠隨心所欲地攻克了。

至于本題的記錄路徑就是編程功底的測試了，不用說什么思路了。不會的僅僅能說編碼能力不行了。

或許也有不懂分析的人也把代碼敲對了，或許是他運氣不錯。或許是他真的是天才級的人物！

反正幾率都非常低，最大幾率還是他的代碼是抄來的。

#include <stdio.h> #include <vector> #include <string.h> #include <algorithm> #include <iostream> #include <string> #include <limits.h> #include <stack> #include <queue> #include <set> #include <map> using namespace std;/* 關鍵理解：僅僅有當下一個格子更新了最小值的時候才須要擴展到這個格子。否則就不須要擴展到這個格子。這個也是相當于廣搜的剪枝點。

理解不了這點的。就沒有透切理解這個問題。 */ namespace IgnatiusandthePrincessI1026 { const int MAX_N = 101; char Maze[MAX_N][MAX_N]; int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}; struct Node { int sec, x, y; Node *p; }; Node mazeRec[MAX_N][MAX_N]; int N, M; inline bool isLegal(int r, int c) { return 0<=r && 0<=c && r<N && c<M && Maze[r][c] != 'X'; } inline int getSec(int r, int c) { if (Maze[r][c] == '.') return 1; return Maze[r][c] - '0' + 1; } void getPath() { for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { mazeRec[i][j].sec = INT_MAX; mazeRec[i][j].x = i, mazeRec[i][j].y = j; mazeRec[i][j].p = NULL; } } queue<Node *> qu; Node *p = &mazeRec[N-1][M-1]; //注意計算錯誤：p->sec = Maze[N-1][M-1] or = getSec(N-1, M-1) p->sec = getSec(N-1, M-1)-1;//終點也可能是有敵人,起點規定了無敵人 qu.push(p); while (!qu.empty()) { p = qu.front(); qu.pop(); for (int i = 0; i < 4; i++) { int tx = p->x + dx[i], ty = p->y + dy[i]; if (!isLegal(tx, ty)) continue; int sec = getSec(tx, ty); Node *tmp = &mazeRec[tx][ty]; if (p->sec+sec < tmp->sec) { tmp->sec = p->sec+sec; tmp->p = p; qu.push(tmp); } /* 關鍵理解：僅僅有當下一個格子更新了最小值的時候才須要擴展到這個格子。否則就不須要擴展到這個格子。這個也是相當于廣搜的剪枝點。

理解不了這點的，就沒有透切理解這個問題。 */ /*各種錯誤教訓！ qu.push(tmp); tmp.vis = true; //錯誤多個else。邏輯錯誤else tmp->vis = true //Maze[tx][ty] = 'X'; tmp.sec = p.sec+sec; tmp.p = &mazeRec[p.x][p.y]; //錯誤：tmp->p = p; //錯誤：tmp->sec = min(tmp->sec, p->sec+sec);*/ } } } int main() { while (~scanf("%d %d", &N, &M)) { while (getchar() != '\n'); for (int i = 0; i < N; i++) { gets(Maze[i]); } getPath(); Node *p = &mazeRec[0][0]; if (p->sec == INT_MAX) puts("God please help our poor hero."); else { printf("It takes %d seconds to reach the target position, let me show you the way.\n", p->sec); int s = 1; for (; p->p; p = p->p) { int x = p->p->x, y = p->p->y; printf("%ds:(%d,%d)->(%d,%d)\n", s++, p->x, p->y, x, y); if (Maze[x][y] == '.') continue; int fig = Maze[x][y] - '0';//錯誤少-'0' for (int i = 0; i < fig; i++) { printf("%ds:FIGHT AT (%d,%d)\n", s++, x, y); } } } puts("FINISH"); } return 0; }

版權聲明：筆者靖心臟。景空間地址：http://blog.csdn.net/kenden23/。只有經過作者同意轉載。

轉載于:https://www.cnblogs.com/yxwkf/p/4754291.html

總結

以上是生活随笔為你收集整理的HDU 1026 Ignatius and the Princess I 迷宫范围内的搜索剪枝问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。