题目描述
小乐乐觉得学习太简单了，剩下那么多的时间好无聊，于是便想打游戏。
最近新出了一个特别火的游戏，叫吃猪，小乐乐准备玩一玩。
吃猪游戏很简单，给定一个地图，大小为n*m，在地图中会随机出现一个火山口，只要小乐乐能逃离这个地图，他便能吃猪！
但吃鸡远没有那么简单：
1.小乐乐每走一次只能上下左右四个方向中走一步。
2.小乐乐每走一步，火山喷发的岩浆就会向四周蔓延一个格子，所有岩浆走过的地方都视为被岩浆覆盖。
3.小乐乐碰到岩浆就会死。
4.地图中还有很多障碍，使得小乐乐不能到达，但是岩浆却可以把障碍融化。
5.小乐乐只有走到题目给定的终点才算游戏胜利，才能吃猪。
小乐乐哪见过这场面，当场就蒙了，就想请帮帮他，告诉他是否能吃猪。
最近新出了一个特别火的游戏，叫吃猪，小乐乐准备玩一玩。
吃猪游戏很简单，给定一个地图，大小为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!"。
输入
3 3 F.. #S# #.E
输出
PIG PIG PIG!
思路：主要是注意火山如何处理，这个题用dfs显然很麻烦，因为要处理火山岩浆，岩浆每走一步扩散四边（四周），所以用bfs更好处理。岩浆先走，这样人就不能走岩浆走过的地方。岩浆走过的地方标记成2，便于岩浆广搜。
处理的时候，要一步处理一步的，不能直接塞到队列里循环。所以要记一下下一步要处理多少位置（新队列元素）。
坑点：
1.四周是上下左右，而不是八个方向。
2.输入的时候注意，一行行输入即可。
1 //注意火山先走，这样便于判断会不会被烫死 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 using namespace std; 6 7 struct node{ 8 int x,y; 9 }; 10 11 char map[1005][1005]; 12 int mark[1005][1005]; 13 int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; 14 int n,m,xf,yf,xs,ys,xe,ye; 15 int flag; 16 17 void bfs(){ 18 queue<node>q; 19 queue<node>p; 20 node head1,next1,head2,next2; 21 head1.x=xs,head1.y=ys; 22 q.push(head1); 23 head2.x=xf,head2.y=yf; 24 p.push(head2); 25 int num1=1,num2=1; 26 27 while(!q.empty()&&!p.empty()){ 28 29 int t2=0; 30 while(num2--){//岩浆 31 head2=p.front(); 32 p.pop(); 33 for(int i=0;i<4;i++){ 34 int xx=head2.x+dir[i][0]; 35 int yy=head2.y+dir[i][1]; 36 if(xx<0||yy<0||xx>=n||yy>=m||mark[xx][yy]==2)continue; 37 mark[xx][yy]=2; 38 t2++; 39 next2.x=xx,next2.y=yy; 40 p.push(next2); 41 } 42 } 43 num2=t2; 44 45 46 int t1=0; 47 while(num1--){//人 48 head1=q.front(); 49 q.pop(); 50 for(int i=0;i<4;i++){ 51 int xx=head1.x+dir[i][0]; 52 int yy=head1.y+dir[i][1]; 53 if(xx==xe&&yy==ye&&mark[xx][yy]==0){ 54 flag=1; 55 return ; 56 } 57 if(xx<0||yy<0||xx>=n||yy>=m||mark[xx][yy]||map[xx][yy]=='#') continue; 58 t1++; 59 mark[xx][yy]=1; 60 next1.x=xx,next1.y=yy; 61 q.push(next1); 62 } 63 } 64 num1=t1; 65 } 66 } 67 68 int main(){ 69 while(~scanf("%d%d",&n,&m)){ 70 71 for(int i=0;i<n;i++){ 72 scanf("%s",map[i]); 73 for(int j=0;j<m;j++){ 74 if(map[i][j]=='F') xf=i,yf=j; 75 if(map[i][j]=='S') xs=i,ys=j; 76 if(map[i][j]=='E') xe=i,ye=j; 77 } 78 } 79 memset(mark,0,sizeof(mark)); 80 mark[xf][yf]=2; 81 mark[xs][ys]=1; 82 flag=0; 83 bfs(); 84 85 if(flag) printf("PIG PIG PIG! "); 86 else printf("A! WO SI LA! "); 87 88 } 89 return 0; 90 }