題干：
?

小樂(lè)樂(lè)覺(jué)得學(xué)習(xí)太簡(jiǎn)單了，剩下那么多的時(shí)間好無(wú)聊，于是便想打游戲。
? ? ? ? 最近新出了一個(gè)特別火的游戲，叫吃豬，小樂(lè)樂(lè)準(zhǔn)備玩一玩。
? ? ? ? 吃豬游戲很簡(jiǎn)單，給定一個(gè)地圖，大小為n*m，在地圖中會(huì)隨機(jī)出現(xiàn)一個(gè)火山口，只要小樂(lè)樂(lè)能逃離這個(gè)地圖，他便能吃豬！?
? ? ? ? 但吃雞遠(yuǎn)沒(méi)有那么簡(jiǎn)單：
????????1.小樂(lè)樂(lè)每走一次只能上下左右四個(gè)方向中走一步。
????????2.小樂(lè)樂(lè)每走一步，火山噴發(fā)的巖漿就會(huì)向四周蔓延一個(gè)格子，所有巖漿走過(guò)的地方都視為被巖漿覆蓋。
????????3.小樂(lè)樂(lè)碰到巖漿就會(huì)死。
????????4.地圖中還有很多障礙，使得小樂(lè)樂(lè)不能到達(dá)，但是巖漿卻可以把障礙融化。
????????5.小樂(lè)樂(lè)只有走到題目給定的終點(diǎn)才算游戲勝利，才能吃豬。
? ? ? ? 小樂(lè)樂(lè)哪見(jiàn)過(guò)這場(chǎng)面，當(dāng)場(chǎng)就蒙了，就想請(qǐng)幫幫他，告訴他是否能吃豬。

輸入描述:

多組樣例輸入第一行給定n,m,(1 <= n, m <= 1000)代表地圖的大小。接下來(lái)n行，每一行m個(gè)字符，代表地圖，對(duì)于每一個(gè)字符，如果是'.'，代表是平地，'S'代表小樂(lè)樂(lè)起始的位置， 'E'代表終點(diǎn)，'#'代表障礙物，'F'代表火山口。

輸出描述:

輸出只有一行。如果小樂(lè)樂(lè)能吃豬，輸出"PIG PIG PIG!"。否則輸出"A! WO SI LA!"。

示例1

輸入

復(fù)制

3 3 F.. #S# #.E

輸出

復(fù)制

PIG PIG PIG!

解題報(bào)告：

? ?之前cf上也做過(guò)一個(gè)類似的、、看題的時(shí)候還真沒(méi)想到這種神奇的做法。。。要是我就直接把火山也讓他蔓延了、、、還是思維不是很巧妙啊、、這兩種方法倒是都沒(méi)啥問(wèn)題，，但是這樣寫就代碼量小很多了。、。改天再那樣寫一遍、、

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; const ll mod=1e9+7; char a[1005][1005]; bool vis[1005][1005]; int t1[5]= {0,0,1,-1}; int t2[5]= {1,-1,0,0}; int n,m,sx,sy,hx,hy;struct note {int x,y,s; }; queue<note> p;int cal(int tx,int ty) {return abs(tx-hx)+abs(ty-hy); }int bfs() {while (p.size()) p.pop();memset(vis,0,sizeof(vis));p.push(note {sx,sy,0});int tx,ty;while (p.size()) {note x=p.front();p.pop();if (a[x.x][x.y]=='E') return 1;if (vis[x.x][x.y]) continue;vis[x.x][x.y]=1;for (int q=0; q<4; q++) {tx=x.x+t1[q];ty=x.y+t2[q];if (tx<0||tx>=n||ty<0||ty>=m) continue;if (vis[tx][ty]||a[tx][ty]=='#') continue;if (x.s+1>=cal(tx,ty)) continue;p.push(note {tx,ty,x.s+1});}}return 0; }int main() {while (scanf("%d%d",&n,&m)==2&&n&&m) {for (int q=0; q<n; q++) {scanf("%s",a[q]);for (int w=0; w<m; w++) {if (a[q][w]=='S') {sx=q;sy=w;}if (a[q][w]=='F') {hx=q;hy=w;}}}if (bfs()) printf("PIG PIG PIG!\n");else printf("A! WO SI LA!\n");}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的*【牛客 - 301哈尔滨理工大学软件与微电子学院第八届程序设计竞赛同步赛（高年级）】小乐乐打游戏（bfs，双元bfs，思维）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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