読者です 読者をやめる 読者になる 読者になる

SRM 590 Div2 Medium FoxAndGo

問題

SRM 590 - TopCoder Wiki

2次元上の盤面に,白石と黒石が置いてある,また少なくとも一つのセルは空である. 黒石を何れかの空セルに置いた時,空セルに隣接していない白石のグループは取り除かれる. この時取り除かれる最大の白石の数を答える問題.

解答

  • シミューレーションして全探索

基本的な実装力を問われる問題. 判定条件をミスしたが,この程度のコードでミスしたくない.

class FoxAndGo
{
public:
  int n;
  vector<vector<char> > b;
  vector <vector<char> > board_temp;
  vector <vector<bool> > used;
  int di[4] = {0, 1, 0, -1};
  int dj[4] = {1, 0, -1, 0};
  bool valid;
  int calc(int ii, int jj){
    int i;
    int res = 0;
    for (i = 0; i < 4; i++){
      int newi = ii + di[i];
      int newj = jj + dj[i];
      if (newi < 0 || newi >= n ||
          newj < 0 || newj >= n) continue;
      if (b[newi][newj] == '.') {
        valid = false;
        continue;
      }
      if (b[newi][newj] == 'o' && !used[newi][newj]){
        used[newi][newj] = true;
        int tmp = calc(newi, newj);
        res += tmp;
      }
    }
    return 1 + res;
  }
  int maxKill(vector <string> board)
    {
      n = board.size();
      int i, j, ii, jj;
      board_temp = vector<vector<char> >(n, vector<char>(n, '-'));
      for(i = 0; i< n; i++) for (j = 0; j< n; j++) this->board_temp[i][j] = board[i][j];
      int res = 0;
      for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++){
          if (board[i][j] != '.') continue;
          b = board_temp;
          used = vector<vector<bool> >(n, vector<bool>(n, false));
          b[i][j] = 'x';
          int count = 0;
          for (ii = 0; ii < n; ii++){
            for(jj = 0; jj < n; jj++){
              valid = true;
              if (b[ii][jj] == 'o' &&
                  !used[ii][jj]) {
                used[ii][jj] = true;
                int tmp = calc(ii, jj);
                if (valid) count += tmp;
              }
            }
          }
          res = max(res, count);
        }
      }
      return res;
    }
};