2013年8月11日

UVa 758 - The Same Game

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

typedef pair<int, int> Pos;

const int dr[6] = {1, 0, -1, 0};
const int dc[6] = {0, 1, 0, -1};
const int R = 10, C = 15;

char map[99][99], temp[99][99];
int size, score;

void travel(char color, int r, int c, bool clear) {
  if (r <= 0 || r > R || c <= 0 || c > C) {
    return;
  }
  if (clear) {
    if (map[r][c] != color) {
      return;
    }
    map[r][c] = 'x';
  } else {
    if (temp[r][c] != color) {
      return;
    }
    temp[r][c] = 'x';
  }
  size++;
  for (int i = 0; i < 4; i++) {
    travel(color, r + dr[i], c + dc[i], clear);
  }
}

Pos getMaxPos() {
  int maxSize = 0;
  memcpy(temp, map, sizeof(map));
  Pos pos;
  for (int c = 1; c <= C; c++) {
    for (int r = 1; r <= R; r++) {
      if (temp[r][c] != 'x') {
        size = 0;
        travel(temp[r][c], r, c, false);
        if (size > maxSize) {
          maxSize = size;
          pos = MP(r, c);
        }
      }
    }
  }
  if (maxSize <= 1) {
    pos.first = 0;
  }
  return pos;
}

void squeeze() {
  char newMap[99][99] = {};
  int shiftLeft = 0;
  for (int c = 1; c <= C; c++) {
    int remain = 0;
    for (int r = 1; r <= R; r++) {
      if (map[r][c] != 'x') {
        newMap[1 + remain++][c - shiftLeft] = map[r][c];
      }
    }
    shiftLeft += !remain;
  }
  for (int r = 1; r <= R; r++) {
    for (int c = 1; c <= C; c++) {
      if (!newMap[r][c]) {
        newMap[r][c] = 'x';
      }
    }
  }
  memcpy(map, newMap, sizeof(newMap));
}

void remove(Pos & pos, int move) {
  int r = pos.first, c = pos.second;
  char color = map[r][c];
  size = 0;
  travel(color, r, c, true);
  int points = (size - 2) * (size - 2);
  score += points;
  printf("Move %d at (%d,%d): removed %d balls of color %c, got %d points.\n", move, r, c, size, color, points);
  squeeze();
}

int main() {
  int T, Case = 1;
  scanf("%d", &T);
  while (T--) {
    for (int r = R; r >= 1; r--) {
      scanf("%s", map[r] + 1);
    }
    printf("Game %d:\n\n", Case++);
    score = 0;
    for (int move = 1; ; move++) {
      Pos pos = getMaxPos();
      if (!(pos.first)) {
        break;
      }
      remove(pos, move);
    }
    int remain = 0;
    for (int r = 1; r <= R; r++) {
      for (int c = 1; c <= C; c++) {
        remain += (map[r][c] != 'x');
      }
    }
    printf("Final score: %d, with %d balls remaining.\n", score + (!remain * 1000), remain);
    if (T) {
      puts("");
    }
  }
  return 0;
}

沒有留言:

張貼留言