本文主要是介绍哈尔滨理工大学软件与微电子学院第八届程序设计竞赛同步赛(高年级)G-小乐乐打游戏(双点BFS),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:https://ac.nowcoder.com/acm/contest/301/G
思路:双点BFS,岩浆和人都放入队列同时进行BFS,注意岩浆可以走障碍物,所以岩浆和人的判断条件不一样,还有岩浆和人同时到达终点应该不能吃猪,所以让岩浆先入队列,还有就是当岩浆先走到终点时就不能吃猪了,直接return。
AC代码:
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f;
const int MAXN = 1005;
int n, m, N, M, dir[4][2] = {{1,0}, {0, 1}, {-1, 0}, {0,-1}};
bool vis[MAXN][MAXN];
struct Point
{int x, y;bool op;
}fire, people, NOW, NEXT;
char MAP[MAXN][MAXN];
bool bfs()
{queue <Point> q;q.push(fire);q.push(people);while(!q.empty()){NOW = q.front();q.pop();if(NOW.op && (NOW.x == M && NOW.y == N)) return true;if(!NOW.op && (NOW.x == M && NOW.y == N)) return false;for(int i = 0; i < 4; i++){int X = NOW.x + dir[i][0], Y = NOW.y + dir[i][1];if(NOW.op){if(X >= 0 && Y >= 0 && X < n && Y < m && MAP[X][Y] != '#' && !vis[X][Y]){vis[X][Y] = true;NEXT.x = X; NEXT.y = Y;NEXT.op = NOW.op;q.push(NEXT);}}else{if(X >= 0 && Y >= 0 && X < n && Y < m && !vis[X][Y]){vis[X][Y] = true;NEXT.x = X; NEXT.y = Y;NEXT.op = NOW.op;q.push(NEXT);}}}}return false;
}
int main()
{memset(vis,false,sizeof(vis));while(~scanf("%d%d", &n, &m)){memset(vis,false,sizeof(vis));for (int i = 0; i < n; i++){for(int j = 0; j < m; j++){cin >> MAP[i][j];if(MAP[i][j] == 'S'){people.x = i; people.y = j;people.op = true;}else if(MAP[i][j] == 'F'){fire.x = i; fire.y = j;fire.op = false;}else if(MAP[i][j] == 'E')M = i, N = j;}}if(bfs()) puts("PIG PIG PIG!");else puts("A! WO SI LA!");}return 0;
}
这篇关于哈尔滨理工大学软件与微电子学院第八届程序设计竞赛同步赛(高年级)G-小乐乐打游戏(双点BFS)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!