*【牛客 - 301哈尔滨理工大学软件与微电子学院第八届程序设计竞赛同步赛（高年级）】小乐乐打游戏（bfs，双元bfs，思维）

题干：
 

小乐乐觉得学习太简单了，剩下那么多的时间好无聊，于是便想打游戏。
        最近新出了一个特别火的游戏，叫吃猪，小乐乐准备玩一玩。
        吃猪游戏很简单，给定一个地图，大小为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!

解题报告：

   之前cf上也做过一个类似的、、看题的时候还真没想到这种神奇的做法。。。要是我就直接把火山也让他蔓延了、、、还是思维不是很巧妙啊、、这两种方法倒是都没啥问题，，但是这样写就代码量小很多了。、。改天再那样写一遍、、

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; }

 

总结

以上是生活随笔为你收集整理的*【牛客 - 301哈尔滨理工大学软件与微电子学院第八届程序设计竞赛同步赛（高年级）】小乐乐打游戏（bfs，双元bfs，思维）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。