【題目描述】

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

下圖 顯示了一個迷陣的樣例及李逍遙找到仙藥的路線。

【輸入】

輸入有多組測試數(shù)據(jù). 每組測試數(shù)據(jù)以兩個非零整數(shù) M 和 N 開始，兩者均不大于20。M 表示迷陣行數(shù), N 表示迷陣列數(shù)。接下來有 M 行, 每行包含N個字符,不同字符分別代表不同含義:

1)‘@’：少年李逍遙所在的位置；

2)‘.’：可以安全通行的方格；

3)‘#’：有怪物的方格；

4)‘*’：仙藥所在位置。

當在一行中讀入的是兩個零時，表示輸入結(jié)束。

【輸出】

對于每組測試數(shù)據(jù)，分別輸出一行，該行包含李逍遙找到仙藥需要穿過的最少的方格數(shù)目(計數(shù)包括初始位置的方塊)。如果他不可能找到仙藥, 則輸出 -1。

【輸入樣例】

8 8
.@##...#
#....#.#
#.#.##..
..#.###.
#.#...#.
..###.#.
...#.*..
.#...###
6 5
.*.#.
.#...
..##.
.....
.#...
....@
9 6

?

.#..#.
.#.*.#
.####.
..#...
..#...
..#...
..#...
#.@.##
.#..#.
0 0

【輸出樣例】

10
8
-1

【源程序】

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 26 #define MOD 2520 #define E 1e-12 using namespace std; int r,c; char a[N][N]; bool vis[N][N]; int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; struct node {int x;int y;int step; }q[N*100]; void bfs(int sx,int sy,int ex,int ey) {int head=1,tail=1;bool flag=true;memset(vis,0,sizeof(vis));vis[sx][sy]=1;q[tail].x=sx;q[tail].y=sy;q[tail].step=0;tail++;while(head<tail){int x=q[head].x;int y=q[head].y;int step=q[head].step;if(x==ex&&y==ey){flag=false;printf("%d\n",step);break;}for(int i=0;i<4;i++){int nx=x+dir[i][0];int ny=y+dir[i][1];if(nx>=0&&nx<r&&ny>=0&&ny<c&&vis[nx][ny]==0&&a[nx][ny]=='.'){vis[nx][ny]=1;q[tail].x=nx;q[tail].y=ny;q[tail].step=step+1;tail++;}}head++;}if(flag)printf("-1\n"); } int main() {int sx,sy,ex,ey;while(scanf("%d%d",&r,&c)!=EOF&&(r||c)){for(int i=0;i<r;i++)scanf("%s",a[i]);for(int i=0;i<r;i++)for(int j=0;j<c;j++){if(a[i][j]=='@'){sx=i;sy=j;}if(a[i][j]=='*'){ex=i;ey=j;a[i][j]='.';}}bfs(sx,sy,ex,ey);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的仙岛求药（信息学奥赛一本通-T1251）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。