Codeforces Round #356 Div2 E: Bear and Square Grid

解法

潰す範囲の正方形を愚直に全部試す。この時、正方形内部の管理を愚直にやると遅くなるので、しゃくとり法の要領で1列ずつやる。

コード

#include <bits/stdc++.h>
using namespace std;

const int DX[] = {0, 0, 1, -1};
const int DY[] = {1, -1, 0, 0};

int N;
vector<int> group_cnt;
vector<string> grid;
vector<vector<int>> group_grid;

bool isInside(int i, int j) { return i >= 0 && j >= 0 && i < N && j < N; }

void DFS(int si, int sj, int group) {
  group_grid[si][sj] = group;
  group_cnt[group]++;
  for (int k = 0; k < 4; ++k) {
    int ni = si + DX[k];
    int nj = sj + DY[k];
    if (!isInside(ni, nj)) continue;
    if (group_grid[ni][nj] != 0 || grid[ni][nj] == 'X') continue;
    DFS(ni, nj, group);
  }
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int K;
  cin >> N >> K;
  grid.resize(N);
  group_grid.assign(N, vector<int>(N, 0));
  group_cnt.assign(N * N + 1, 0);
  for (int i = 0; i < N; ++i) cin >> grid[i];

  // 連結成分にIDを振っていき、同時に数も数えておく
  int group = 1;
  for (int i = 0; i < N; ++i)
    for (int j = 0; j < N; ++j)
      if (group_grid[i][j] == 0 && grid[i][j] == '.') DFS(i, j, group++);

  int best_ans = 0;
  for (int h_low = 0; h_low + K <= N; ++h_low) {
    // 最初、正方形を左端に置く
    // 正方形の内部に含まれるマスの数を除いておく
    for (int h = h_low; h < h_low + K; ++h)
      for (int w = 0; w < K; ++w) group_cnt[group_grid[h][w]]--;

    for (int w_low = 0; w_low + K <= N; ++w_low) {
      int ans = K * K;
      vector<int> merged_groups;

      // 正方形に接している連結成分を列挙する
      for (int h = h_low; h < h_low + K; ++h) {
        if (w_low - 1 >= 0 && group_grid[h][w_low - 1])
          merged_groups.push_back(group_grid[h][w_low - 1]);
        if (w_low + K < N && group_grid[h][w_low + K])
          merged_groups.push_back(group_grid[h][w_low + K]);
      }
      for (int w = w_low; w < w_low + K; ++w) {
        if (h_low - 1 >= 0 && group_grid[h_low - 1][w])
          merged_groups.push_back(group_grid[h_low - 1][w]);
        if (h_low + K < N && group_grid[h_low + K][w])
          merged_groups.push_back(group_grid[h_low + K][w]);
      }

      sort(merged_groups.begin(), merged_groups.end());
      merged_groups.erase(unique(merged_groups.begin(), merged_groups.end()),
                          merged_groups.end());

      for (int g : merged_groups)
        if (g > 0) ans += group_cnt[g];
      best_ans = max(best_ans, ans);

      // 正方形を1マス右に動かす。しゃくとり法の要領で潰されるマスと潰されないマスを更新する。
      if (w_low + K < N)
        for (int h = h_low; h < h_low + K; ++h) {
          group_cnt[group_grid[h][w_low]]++;
          group_cnt[group_grid[h][w_low + K]]--;
        }
    }

    // 正方形が右端まで行ったら、一端正方形を取り除くので潰されたマスを元に戻す
    for (int h = h_low; h < h_low + K; ++h)
      for (int w = N - K; w < N; ++w) group_cnt[group_grid[h][w]]++;
  }
  cout << best_ans << endl;
}