时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
小乐乐觉得学习太简单了，剩下那么多的时间好无聊，于是便想打游戏。
最近新出了一个特别火的游戏，叫吃猪，小乐乐准备玩一玩。
吃猪游戏很简单，给定一个地图，大小为n*m，在地图中会随机出现一个火山口，只要小乐乐能逃离这个地图，他便能吃猪！
但吃鸡远没有那么简单：
1.小乐乐每走一次只能上下左右四个方向中走一步。
2.小乐乐每走一步，火山喷发的岩浆就会向四周蔓延一个格子，所有岩浆走过的地方都视为被岩浆覆盖。
3.小乐乐碰到岩浆就会死。
4.地图中还有很多障碍，使得小乐乐不能到达，但是岩浆却可以把障碍融化。
5.小乐乐只有走到题目给定的终点才算游戏胜利，才能吃猪。
小乐乐哪见过这场面，当场就蒙了，就想请帮帮他，告诉他是否能吃猪。
输入描述:
多组样例输入
第一行给定n,m,(1 <= n, m <= 1000)代表地图的大小。
接下来n行，每一行m个字符，代表地图，对于每一个字符，如果是'.'，代表是平地，'S'代表小乐乐起始的位置，
'E'代表终点，'#'代表障碍物，'F'代表火山口。输出描述:
输出只有一行。如果小乐乐能吃猪，输出"PIG PIG PIG!"。否则输出"A! WO SI LA!"。示例1
输入
3 3
F..
#S#
#.E输出
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");
}
}