2013年8月12日

UVa 11561 - Getting Gold

#include <cstdio>
#include <queue>
#define MP make_pair
using namespace std;

typedef pair<int, int> P;

const int dr[4] = {1, 0, -1, 0};
const int dc[4] = {0, 1, 0, -1};

int main() {
  int R, C;
  while (scanf("%d%d", &C, &R) == 2) {
    char map[99][99] = {};
    bool visit[99][99] = {};
    queue<P> q;
    for (int r = 1; r <= R; r++) {
      scanf("%s", map[r] + 1);
      for (int c = 1; c <= C; c++) {
        if (map[r][c] == 'P') {
          q.push(MP(r, c));
          visit[r][c] = true;
        }
      }
    }
    int ans = 0;
    while (!q.empty()) {
      int r = q.front().first, c = q.front().second;
      q.pop();
      ans += (map[r][c] == 'G');
      bool danger = false;
      for (int i = 0; i < 4; i++) {
        if (map[r + dr[i]][c + dc[i]] == 'T') {
          danger = true;
        }
      }
      if (danger) {
        continue;
      }
      for (int i = 0; i < 4; i++) {
        int nr = r + dr[i], nc = c + dc[i];
        if (!visit[nr][nc] && (map[nr][nc] == 'G' || map[nr][nc] == '.')) {
          q.push(MP(nr, nc));
          visit[nr][nc] = true;
        }
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

沒有留言:

張貼留言