總時間限制: 1000ms 記憶體限制: 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”
樣例輸入
樣例輸出
13
7
我用了記憶化搜索，能求出第一個例子，但沒法ac，求大佬看看哪的問題
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int s;
int n, m;
char mg[210][210]; //迷宮
int v[210][210]; //判斷陣列
int rx, ry; //起點
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int ds[210][210]; // 某點到終點最小距離
int dfs(int x, int y){
if(ds[x][y]) return ds[x][y];
if(mg[x][y] == 'a') return 0;
int temp = 1 << 30;
for(int i = 0; i < 4; i++){
int x1 = x + dx[i];
int y1 = y + dy[i];
if(!v[x1][y1]){
if(mg[x1][y1] == '#') continue;
else{
v[x1][y1] = 1;
temp = min(temp, dfs(x1, y1));
v[x1][y1] = 0;
}
}
}
if(mg[x][y] == 'x') ds[x][y] = temp + 2;
else ds[x][y] = temp + 1;
return ds[x][y];
}
int main(){
cin >> s;
while(s--){
cin >> n >> m;
memset(mg, '#', sizeof(mg));
memset(v, 0, sizeof(v));
memset(ds, 0, sizeof(ds));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> mg[i][j];
if(mg[i][j] == 'r'){
rx = i;
ry = j;
}
}
}
v[rx][ry] = 1;
int ans = dfs(rx, ry);
if(ans >= 1 << 30) cout << "Impossible" << endl;
else cout << ans << endl;
}
return 0;
}
uj5u.com熱心網友回復：
最短路徑是BFS，用到佇列結構用DFS還要繼續搜下去，用的系統的堆疊， 遍歷所有結果再回傳啊，否則你無法認定你達到的路徑是最短的，只能證明達到過
uj5u.com熱心網友回復：
bfs加優先佇列的確是最優方法，我這個dfs用陣列記憶某點到終點的最短路徑長度，不用陣列直接遞回會超時
uj5u.com熱心網友回復：
超時就是演算法本身的問題啦不是找不到答案而是不夠快
用記憶最短路徑不是不可以，從目標點出發，反過來向周邊擴散，寫入到達目標點的最短距離， 直到遇到起點，可這個程序也是bfs啊
用dfs還是同一個問題，不完成遍歷就不知道最優結果
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/110123.html
標籤：C++ 語言
上一篇：計算機科學概論
下一篇：演算法設計與分析 求助