時(shí)間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 32768K，其他語言65536K
64bit IO Format: %lld

題目描述

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

輸入描述:

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

輸出描述:

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

?

示例1

輸入

復(fù)制

3 3
F..
#S#
#.E

輸出

復(fù)制

PIG PIG PIG!

代碼：

#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-48,ch=getchar();}return x*f;
}
const int maxn = 1010;
char s[maxn][maxn];
struct edge{int to,next;
}e[maxn*maxn*2];
int tot,head[maxn*maxn];
void add(int u,int v){e[++tot].to=v;e[tot].next=head[u];head[u]=tot;
}
int dis[maxn*maxn],num[maxn][maxn],S,T,Fx,Fy;
int tim[maxn*maxn];
int dx[]={0,1,-1,0,0};
int dy[]={0,0,0,1,-1};
int main()
{int n,m,cnt=0;while(scanf("%d%d",&n,&m)!=EOF){cnt=0,tot=0;memset(head,0,sizeof head);for(int i=1;i<=n;i++){scanf("%s",s[i]+1);for(int j=1;j<=m;j++){num[i][j]=++cnt;if(s[i][j]=='S') S=cnt;if(s[i][j]=='E') T=cnt;if(s[i][j]=='F') Fx=i,Fy=j;}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){tim[num[i][j]]=abs(Fx-i)+abs(Fy-j);if(s[i][j]=='#')continue;for(int k=1;k<=4;k++){int x=i+dx[k],y=j+dy[k];if(x<=0||y<=0||x>n||y>m||s[x][y]=='#')continue;add(num[i][j],num[x][y]);}}}queue<int>q;memset(dis,0x3f,sizeof dis);q.push(S);dis[S]=0;while(!q.empty()){int x=q.front();q.pop();for(int i=head[x];i;i=e[i].next){int to=e[i].to;if(dis[x]+1>=tim[to]) continue;if(dis[to]>dis[x]+1){q.push(to);dis[to]=dis[x]+1;}}}if(dis[T]==0x3f3f3f3f) printf("A! WO SI LA!\n");else printf("PIG PIG PIG!\n");}
}

?

轉(zhuǎn)載于:https://www.cnblogs.com/Staceyacm/p/10782059.html

總結(jié)

以上是生活随笔為你收集整理的小乐乐打游戏（BFS+曼哈顿距离）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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