1256：獻(xiàn)給阿爾吉儂的花束

時(shí)間限制: 1000 ms ??? ??? 內(nèi)存限制: 65536 KB
提交數(shù): 9651 ??? 通過(guò)數(shù): 4023

【題目描述】

阿爾吉儂是一只聰明又慵懶的小白鼠，它最擅長(zhǎng)的就是走各種各樣的迷宮。今天它要挑戰(zhàn)一個(gè)非常大的迷宮，研究員們?yōu)榱斯膭?lì)阿爾吉儂盡快到達(dá)終點(diǎn)，就在終點(diǎn)放了一塊阿爾吉儂最喜歡的奶酪。現(xiàn)在研究員們想知道，如果阿爾吉儂足夠聰明，它最少需要多少時(shí)間就能吃到奶酪。

迷宮用一個(gè)R×C的字符矩陣來(lái)表示。字符S表示阿爾吉儂所在的位置，字符E表示奶酪所在的位置，字符#表示墻壁，字符.表示可以通行。阿爾吉儂在1個(gè)單位時(shí)間內(nèi)可以從當(dāng)前的位置走到它上下左右四個(gè)方向上的任意一個(gè)位置，但不能走出地圖邊界。

【輸入】

第一行是一個(gè)正整數(shù)T（1 ≤ T ≤ 10），表示一共有T組數(shù)據(jù)。

每一組數(shù)據(jù)的第一行包含了兩個(gè)用空格分開(kāi)的正整數(shù)R和C（2 ≤ R, C ≤ 200），表示地圖是一個(gè)R×C的矩陣。

接下來(lái)的R行描述了地圖的具體內(nèi)容，每一行包含了C個(gè)字符。字符含義如題目描述中所述。保證有且僅有一個(gè)S和E。

【輸出】

對(duì)于每一組數(shù)據(jù)，輸出阿爾吉儂吃到奶酪的最少單位時(shí)間。若阿爾吉儂無(wú)法吃到奶酪，則輸出“oop!”（只輸出引號(hào)里面的內(nèi)容，不輸出引號(hào)）。每組數(shù)據(jù)的輸出結(jié)果占一行。

【輸入樣例】

3 3 4 .S.. ###. ..E. 3 4 .S.. .E.. .... 3 4 .S.. #### ..E.

【輸出樣例】

5 1 oop!

【AC代碼】

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e3+10; const int INF=0x3f3f3f3f; inline int read() {char ch=getchar();int n=0,m=1;while(ch<'0'||ch>'9'){if(ch=='-')m=-1;ch=getchar();}while(ch>='0'&&ch<='9')n=(n<<3)+(n<<1)+ch-48,ch=getchar();return n*m; } void write(int n) {if(n>9)write(n/10);putchar(n%10+'0'); } int t,r,c,sx,sy,dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; char m[N][N]; bool vis[N][N]; struct point {int px,py,pt; }; queue<point> q; void bfs(int tx,int ty,int tt) {q.push((point){tx,ty,tt});vis[tx][ty]=1;while(!q.empty()){point p=q.front();q.pop();if(m[p.px][p.py]=='E'){cout<<p.pt<<"\n";return;}for(int i=0;i<4;i++){int nx=p.px+dir[i][0],ny=p.py+dir[i][1];if(nx>0&&nx<=r&&ny>0&&ny<=c&&m[nx][ny]!='#'&&vis[nx][ny]==0){q.push((point){nx,ny,p.pt+1});vis[nx][ny]=1;}}}cout<<"oop!\n"; } int main(int argc,char **argv) {t=read();while(t--){r=read(),c=read();memset(vis,0,sizeof vis);memset(m,'\0',sizeof m);while(!q.empty())q.pop();for(int i=1;i<=r;i++)for(int j=1;j<=c;j++){cin>>m[i][j];if(m[i][j]=='S')sx=i,sy=j;}bfs(sx,sy,0);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的1256：献给阿尔吉侬的花束的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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