2012年11月12日

UVa 785 - Grid Colouring


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

typedef pair<int, int> P;

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

int main() {
  int n;
  char grid[100][100];
  while (gets(grid[0]) != NULL) {
    set<P> ok;
    map<P, int> visit;
    queue<pair<P, char> > start;
    int r, c, r0, c0;
    for (r = 1; ; r++) {
      gets(grid[r]);
      if (grid[r][0] == '_') break;
      for (c = 0; grid[r][c]; c++) {
        if (grid[r][c] != 'X') ok.insert(MP(r, c));
        if (grid[r][c] != 'X' && grid[r][c] != ' ') {
          ok.insert(MP(r, c));
          start.push(MP(MP(r, c), grid[r][c]));
        }
      }
    }
    while (!start.empty()) {
      queue<P> q;
      q.push(MP(start.front().first.first, start.front().first.second));
      char ch = start.front().second;
      while (!q.empty()) {
        int r = q.front().first, c = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
          P p = MP(r + dr[i], c + dc[i]);
          if (visit.count(p) || !ok.count(p)) continue;
          grid[r + dr[i]][c + dc[i]] = ch;
          q.push(p);
          visit[p] = 1;
        }
      }
      start.pop();
    }
    for (r = 0; ; r++) {
      puts(grid[r]);
      if (grid[r][0] == '_') break;
    }
  }
  return 0;
}

沒有留言:

張貼留言