2013年4月9日

UVa 657 - The die is cast


#include <cstdio>
#include <vector>
#include <algorithm>

int w, h, cnt;
char map[99][99];
std::vector<int> ans;

void clear(int r, int c) {
  if (r < 0 || c < 0 || r >= h || c >= w ||map[r][c] != 'X') return;
  map[r][c] = '.';
  clear(r + 1, c);
  clear(r - 1, c);
  clear(r, c + 1);
  clear(r, c - 1);
}

void run(int r, int c) {
  if (r < 0 || c < 0 || r >= h || c >= w ||map[r][c] == '.') return;
  if (map[r][c] == 'X') {
    cnt++;
    clear(r, c);
  }
  map[r][c] = '.';
  run(r + 1, c);
  run(r - 1, c);
  run(r, c + 1);
  run(r, c - 1);
}

int main() {
  int T = 1;
  while (scanf("%d%d", &w, &h) && w || h) {
    ans.clear();
    int r, c;
    for (r = 0; r < h; r++)
      scanf("%s", map[r]);
    for (r = 0; r < h; r++)
      for (c = 0; c < w; c++)
        if (map[r][c] == '*' || map[r][c] == 'X') {
          cnt = 0;
          run(r, c);
          if (cnt) ans.push_back(cnt);
        }
    std::sort(ans.begin(), ans.end());
    printf("Throw %d\n", T++);
    for (r = 0; r < ans.size(); r++)
      printf("%d%s", ans[r], r == ans.size() - 1 ? "\n\n" : " ");
  }
  return 0;
}

沒有留言:

張貼留言