仙島求藥（BFS迷宮尋找最短路徑）

2019-11-08 18:41:57

字體：大中小

來源：轉載

供稿：網友

描述少年李逍遙的嬸嬸病了，王小虎介紹他去一趟仙靈島，向仙女姐姐要仙丹救嬸嬸。叛逆但孝順的李逍遙闖進了仙靈島，克服了千險萬難來到島的中心，發現仙藥擺在了迷陣的深處。迷陣由M×N個方格組成，有的方格內有可以瞬秒李逍遙的怪物，而有的方格內則是安全。現在李逍遙想盡快找到仙藥，顯然他應避開有怪物的方格，并經過最少的方格，而且那里會有神秘人物等待著他。現在要求你來幫助他實現這個目標。下圖顯示了一個迷陣的樣例及李逍遙找到仙藥的路線.

輸入輸入有多組測試數據. 每組測試數據以兩個非零整數 M 和 N 開始，兩者均不大于20。M 表示迷陣行數, N 表示迷陣列數。接下來有 M 行, 每行包含N個字符,不同字符分別代表不同含義: 1) ‘@’：少年李逍遙所在的位置；2) ‘.’：可以安全通行的方格；3) ‘#’：有怪物的方格；4) ‘*’：仙藥所在位置。當在一行中讀入的是兩個零時，表示輸入結束。輸出對于每組測試數據，分別輸出一行，該行包含李逍遙找到仙藥需要穿過的最少的方格數目(計數包括初始位置的方塊)。如果他不可能找到仙藥, 則輸出 -1。樣例輸入

8 8.@##...##....#.##.#.##....#.###.#.#...#...###.#....#.*...#...###6 5.*.#..#.....##.......#.......@9 6.#..#. .#.*.# .####. ..#... ..#... ..#... ..#... #.@.## .#..#. 0 0樣例輸出108-1
之前寫了一個深搜，在做后面的題目時用深搜肯定超時超時超時，索性直接寫個廣搜，因為我感覺深搜好理解一些，一直遍歷一直遍歷找到最短的。廣搜就直接遍歷一次，使得下一次到達的點都是最小的。這樣就很好的和隊列（先進先出）結合起來。通俗的說就是到達一個點，這個點會同時走4個方向，但是深搜的話走一個方向只有到這條路沒法走或者到終點才會返回上一個路口。從起點到終點就是建立隊列的過程
1.從起點開始，先將其加入隊列，設置步數為0
2.從隊列首端取出位置，將從這個位置能夠到達的位置加入隊列，并且讓這些位置的距離為上一個位置的距離加上1
3.循環2直到從隊列首端取出的是終點
最簡單的理解方法就是畫圖，結合隊列的先進先出，每到達一個點
#include<iostream>#include<queue>using namespace std;typedef pair<int, int> P;int n, m, q1, q2, z1, z2;char a[21][21];int pd(int i, int j){	if (i < 0 || j < 0 || i >= n || j >= m || a[i][j] == '#')//不能出邊界		return 0;	return 1;}int main(){	while (1){		int map[21][21];		cin >> n >> m;		if (n == 0 && m == 0)			break;		for (int i = 0; i < n; i++){			for (int j = 0; j < m; j++){				cin >> a[i][j];				map[i][j] = 1000;				if (a[i][j] == '@'){					q1 = i; q2 = j;				}				if (a[i][j] == '*'){					z1 = i; z2 = j;				}			}		}		queue<P> que;		map[q1][q2] = 0;		que.push(P(q1, q2));//將起點入隊列		while (que.size()) {			P p = que.front(); //取得頭元素			que.pop();			if (p.first == z1&&p.second == z2)				break;			if (pd(p.first + 1, p.second) && map[p.first + 1][p.second] == 1000){//如果地圖上某一點已經走過了，那就不用走了，肯定有別的方法到達它更短				map[p.first + 1][p.second] = map[p.first][p.second] + 1;//因為在每次處理的位置都是遞增的。走過的路不用走了，也映證了廣搜				que.push(P(p.first + 1, p.second));			}			if (pd(p.first - 1, p.second) && map[p.first - 1][p.second] == 1000){				map[p.first - 1][p.second] = map[p.first][p.second] + 1;				que.push(P(p.first - 1, p.second));			}			if (pd(p.first, p.second + 1) && map[p.first][p.second + 1] == 1000){				map[p.first][p.second + 1] = map[p.first][p.second] + 1;				que.push(P(p.first, p.second + 1));			}			if (pd(p.first, p.second - 1) && map[p.first][p.second - 1] == 1000){				map[p.first][p.second - 1] = map[p.first][p.second] + 1;				que.push(P(p.first, p.second - 1));			}		}		if (map[z1][z2] == 1000)			PRintf("-1/n");		else			printf("%d/n", map[z1][z2]);	}	return 0;}先結合圖理解代碼。有好的思想一起交流
實在不懂了就可以先看下：抓住那頭牛。這道題的廣搜就簡單很多http://blog.csdn.net/QQ_33193309/article/details/55260780