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; }