网站运营及推广/南京百度快速排名优化

题目链接：uva 11561 - Getting Gold

题目大意：就是一张图，每次走到陷阱周围，为了防止调入陷阱，会停止前进，问说最多能收集多少黄金。

解题思路：bfs，将陷阱周围标记，走到就停止即可。

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>using namespace std;
const int maxn = 55;
const int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
typedef pair<int, int> pii;int W, H, v[maxn][maxn];
char g[maxn][maxn];void tiger (int x, int y) {for (int i = 0; i < 4; i++) {int p = x + dir[i][0];int q = y + dir[i][1];if (p < 0 || p >= H || q < 0 || q >= W)continue;if (v[p][q] == 0)v[p][q] = -1;}
}int bfs (pii s) {int ret = 0;if (v[s.first][s.second] == -1)return 0;queue<pii> que;que.push(s);while (!que.empty()) {int x = que.front().first;int y = que.front().second;que.pop();for (int i = 0; i < 4; i++) {int p = x + dir[i][0];int q = y + dir[i][1];if (p < 0 || p >= H || q < 0 || q >= W || v[p][q] == 1 || g[p][q] == '#')continue;if (v[p][q] != -1)que.push(make_pair(p, q));v[p][q] = 1;if (g[p][q] == 'G')ret++;}}return ret;
}int main () {while (scanf("%d%d", &W, &H) == 2) {memset(v, 0, sizeof(v));for (int i = 0; i < H; i++)scanf("%s", g[i]);pii s;for (int i = 0; i < H; i++) {for (int j = 0; j < W; j++) {if (g[i][j] == 'P')s = make_pair(i, j);else if (g[i][j] == 'T')tiger(i, j);}}printf("%d\n", bfs(s));}return 0;
}