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

SRM 578 Div2 Medium GooseInZooDivTwo

問題

SRM 578 - TopCoder Wiki

檻の中に鳥が複数匹いる.タイルがあって一つのタイルには鳥は一匹までしか入れない. 鳥はgooseとducksがいる. - gooseは少なくとも一匹いる. - gooseのマンハッタン距離dist以内の鳥は必ずgoose

解答

  • マンハッタン距離dist以内の鳥はグループと考える.というのはそのグループは全部gooseか,全部ducksの2通りしか無いから.
  • グループ分けをした結果K個のグループがあればgooseの組み合わせは2K-1(gooseは必ず一匹入るので-1)
  • 後はoverflowに気をつけながら計算すれば良い.
class GooseInZooDivTwo
{
public:
  int n, m;
  vector<vector<bool> > field;
  int dist;
  void delgroup(int row, int col) {
    for (int d_row = -dist; d_row <= dist; d_row++){
      for (int d_col = -dist; d_col <= dist; d_col++) {
        if (abs(d_row) + abs(d_col) <= dist) {
          int new_row = row + d_row;
          int new_col = col + d_col;
          if (0 <= new_row && new_row < n &&
              0 <= new_col && new_col < m &&
              field[new_row][new_col]){
            // cout << "del row=" << row << " col=" << col << endl;
            field[new_row][new_col] = false;
            delgroup(new_row, new_col);
          }
        }
      }
    }
  }
  int count(vector <string> field, int dist)
    {
      n = field.size();
      m = field[0].size();
      this->dist = dist;
      this->field = vector<vector<bool> >(n, vector<bool>(m, false));
      for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
          if (field[i][j] == 'v') this->field[i][j] = true;
        }
      }
      int num_group = 0;
      for(int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
          // cout << "field[" << i << "][" << j << "]=" << this->field[i][j] << endl;
          if (this->field[i][j]) {
            num_group++;
            delgroup(i, j);
          }
        }
      }
      cout << "num_group=" << num_group << endl;
      long long digit = 1;
      for (int i = 0; i < num_group; i++) digit = (digit * 2) % 1000000007;
      return (digit-1 + 1000000007) % 1000000007;
    }
};