題目描述
少年李逍遙的嬸嬸病了，王小虎介紹他去一趟仙靈島，向仙女姐姐要仙丹救嬸嬸。
叛逆但孝順的李逍遙闖進了仙靈島，克服了千險萬難來到島的中心，發現仙藥擺在了迷陣的深處。
迷陣由 M × N 個方格組成，有的方格内有可以瞬秒李逍遙的怪物，而有的方格内則是安全。
現在李逍遙想盡快找到仙藥，顯然他應避開有怪物的方格，并經過最少的方格，而且那裡會有神秘人物等待着他。
現在要求你來幫助他實作這個目标。下圖顯示了一個迷陣的樣例及李逍遙找到仙藥的路線。
輸入格式
輸入有多組測試資料. 每組測試資料以兩個非零整數 M 和 N 開始，兩者均不大于 20。
M 表示迷陣行數, N 表示迷陣列數。接下來有 M 行, 每行包含 N 個字元,不同字元分别代表不同含義:
-
@
-
.
-
#
-
*
當在一行中讀入的是兩個零時，表示輸入結束。
輸出格式
對于每組測試資料，分别輸出一行，該行包含李逍遙找到仙藥需要穿過的最少的方格數目(計數包括初始位置的方塊)。
如果他不可能找到仙藥, 則輸出 -1。
輸入樣例
8 8
.@##...#
#....#.#
#.#.##..
..#.###.
#.#...#.
..###.#.
...#.*..
.#...###
6 5
.*.#.
.#...
..##.
.....
.#...
....@
9 6
.#..#.
.#.*.#
.####.
..#...
..#...
..#...
..#...
#.@.##
.#..#.
0 0
輸出樣例
10
8
-1
題解
BFS：
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
struct node{
int x, y;
}S;
const int N = 30;
int n, m;
char g[N][N];
int dist[N][N];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int bfs()
{
memset(dist, -1, sizeof dist);
queue<node> q;
q.push(S);
dist[S.x][S.y] = 0;
while(q.size())
{
node t = q.front();
q.pop();
if(g[t.x][t.y] == '*') return dist[t.x][t.y];
for (int i = 0; i < 4; i ++)
{
int a = t.x + dx[i], b = t.y + dy[i];
if(a < 1 || a > n || b < 1 || b > m) continue;
if(dist[a][b] != -1 || g[a][b] == '#') continue;
q.push({a, b});
dist[a][b] = dist[t.x][t.y] + 1;
}
}
return -1;
}
int main()
{
while(cin >> n >> m, n || m)
{
for (int i = 1; i <= n; i ++) cin >> g[i] + 1;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
if(g[i][j] == '@') S = {i, j};
cout << bfs() << endl;
}
return 0;
}
ps：如果定義的是全局隊列，每次輸入前要把之前的隊列清空。