2013年8月16日

UVa 639 - Don't Get Rooked

#include <cstdio>
#include <string>
#include <vector>
#define PB push_back
using namespace std;

int ans;

void solve(vector<string> & board, int num) {
  ans = num > ans ? num : ans;
  for (int r = 0; r < board.size(); r++) {
    for (int c = 0; board[r][c]; c++) {
      if (board[r][c] == '.') {
        vector<string> next(board);
        for (int w = c; w >= 0; w--) {
          if (next[r][w] != 'X') {
            next[r][w] = false;
          } else {
            break;
          }
        }
        for (int w = c; next[r][w]; w++) {
          if (next[r][w] != 'X') {
            next[r][w] = false;
          } else {
            break;
          }
        }
        for (int h = r; h >= 0; h--) {
          if (next[h][c] != 'X') {
            next[h][c] = false;
          } else {
            break;
          }
        }
        for (int h = r; h < board.size(); h++) {
          if (next[h][c] != 'X') {
            next[h][c] = false;
          } else {
            break;
          }
        }
        solve(next, num + 1);
      }
    }
  }
}

int main() {
  int n;
  while (scanf("%d", &n) && n) {
    vector<string> board;
    while (n--) {
      char row[99];
      scanf("%s", row);
      board.PB(row);
    }
    ans = 0;
    solve(board, 0);
    printf("%d\n", ans);
  }
  return 0;
}

沒有留言:

張貼留言