總時間限制: 10000ms 內存限制: 65536kB
描述
公主被惡人抓走，被關押在牢房的某個地方。牢房用N*M (N, M <= 200)的矩陣來表示。矩陣中的每項可以代表道路（@）、墻壁（#）、和守衛（x）。
英勇的騎士（r）決定孤身一人去拯救公主（a）。我們假設拯救成功的表示是“騎士到達了公主所在的位置”。由于在通往公主所在位置的道路中可能遇到守衛，騎士一旦遇到守衛，必須殺死守衛才能繼續前進。
現假設騎士可以向上、下、左、右四個方向移動，每移動一個位置需要1個單位時間，殺死一個守衛需要花費額外的1個單位時間。同時假設騎士足夠強壯，有能力殺死所有的守衛。

給定牢房矩陣，公主、騎士和守衛在矩陣中的位置，請你計算拯救行動成功需要花費最短時間。

輸入
第一行為一個整數S，表示輸入的數據的組數（多組輸入）
隨后有S組數據，每組數據按如下格式輸入
1、兩個整數代表N和M, (N, M <= 200).
2、隨后N行，每行有M個字符。”@”代表道路，”a”代表公主，”r”代表騎士，”x”代表守衛, “#”代表墻壁。
輸出
如果拯救行動成功，輸出一個整數，表示行動的最短時間。
如果不可能成功，輸出”Impossible”
樣例輸入
（輸入gg了，想看的直接看原題吧，http://bailian.openjudge.cn/practice/4116/）
樣例輸出
13
7

題解：BFS做這道題，與往常不同的是，這道題的answer會更新，不能遇見a就輸出，而且如果遇到x，step加的是2，不是1。而且由于各個節點會更新，所以沒有vis數組，這時候就要根據此種方法是否能夠使結果更優來判斷是否繼續。

思考：
1、一道簡單題做了1天，還是太弱。
2、可以用結構體存儲到現在的步數。
3、由于路徑不同，所以可能結果會更新，不能看到a就退出。
4、要用一個數組存儲到達每一個節點的最短時間，如果需要更新再push等等，如果不需要更新，就不用push。

#include <iostream> #include <cstdio> #include <string> #include <algorithm> #include <cstring> #include <cmath> #include <vector> #include <map> #include <set> #include <queue>using namespace std;struct point {int x, y, step;point(int xx, int yy, int s) : x(xx), y(yy), step(s) {} };const int maxn = 205; const int INF = 1 << 30; char maze[maxn][maxn]; int time1[maxn][maxn], dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int n, m, answer; point r(0, 0, 0);void BFS() {queue<point> q;q.push(r);time1[r.x][r.y] = 0;//記錄到達這個地方的上一個節點需要多長時間while (!q.empty()){point now = q.front();q.pop();if (maze[now.x][now.y] == 'a')//由于是在結構體里面存儲的是走到這個地方所需時間，所以要在這里判斷{answer = min (answer, now.step);}else{for (int i = 0; i < 4; i++){int tempx = now.x + dir[i][0];int tempy = now.y + dir[i][1];if (tempx < 1 || tempx > n || tempy < 1 || tempy > m || maze[tempx][tempy] == '#' || now.step >= time1[tempx][tempy] || now.step >= answer) continue;//如果超邊界或者到上一步時所需時間已經比原來的更大，則跳if (maze[tempx][tempy] == 'x'){time1[tempx][tempy] = now.step;//記錄到達上一個狀態所需時間q.push(point(tempx, tempy, now.step + 2));//step里面記錄到達這個狀態所需時間}else{time1[tempx][tempy] = now.step;q.push(point(tempx, tempy, now.step + 1));}}}} }int main() { #ifndef ONLINE_JUDGEfreopen ("in.txt", "r", stdin); #endif // ONLINE_JUDGEint t;scanf ("%d", &t);while (t--){memset (maze, '\0', sizeof(maze));answer = INF;scanf ("%d%d", &n, &m);for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> maze[i][j];if (maze[i][j] == 'r'){r.x = i;r.y = j;r.step = 0;}time1[i][j] = INF;}}BFS ();if (answer == INF){printf ("Impossible");}else{printf ("%d", answer);}if (t != 0) printf ("\n");}return 0; }

總結

以上是生活随笔為你收集整理的拯救行动（变种bfs）的全部內容，希望文章能夠幫你解決所遇到的問題。

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