鏈接：https://ac.nowcoder.com/acm/contest/301/G
來源：牛客網(wǎng)

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

題目描述

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

輸入描述:

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

輸出描述:

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

輸入

3 3
F..
#S#
#.E

輸出

PIG PIG PIG!

解題思路

這道題其實就是讓你判斷一下巖漿和小樂樂誰先到達(dá)終點(diǎn)。直接用BFS搜索一下就行了，只要巖漿到終點(diǎn)的距離小于小樂樂到終點(diǎn)的距離，那么小樂樂肯定是到不了的。注意一下巖漿的距離是怎樣求的。

#include <queue> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> using namespace std; const int N = 1005; const int inf = 99999999; int n, m, ex, ey, len; int map[N][N], vis[N][N]; int nex[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; struct edge {int u, v, flag; }t; int BFS(int u, int v) {vis[u][v] = 1;queue <edge> Q;Q.push((edge){u, v, 0});while (!Q.empty()) {t = Q.front();Q.pop();for (int i = 0; i < 4; i++) {int tx = t.u + nex[i][0];int ty = t.v + nex[i][1];if (t.flag + 1 > len)return inf;if (tx == ex && ty == ey)return t.flag + 1;if (tx < 0 || tx >= n || ty < 0 || ty >= m)continue;if (map[tx][ty] && !vis[tx][ty]) {vis[tx][ty] = 1;Q.push((edge){tx, ty, t.flag + 1});}}}return inf; } int main() {char s[N];int ans, sx, sy, px, py;while (~scanf("%d%d", &n, &m)) {memset(vis, 0, sizeof(vis));for (int i = 0; i < n; i++) {scanf("%s", s);for (int j = 0; j < m; j++) {if (s[j] != '#') {map[i][j] = 1;switch (s[j]) {case 'S': sx = i; sy = j; break;case 'E': ex = i; ey = j; break;case 'F': px = i; py = j; break;}}else map[i][j] = 0;}}len = abs(px - ex) + abs(py - ey);ans = BFS(sx, sy);if (ans <= len)printf("PIG PIG PIG!\n");else printf("A! WO SI LA!\n");}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的牛客网 - 小乐乐打游戏(BFS)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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