Codeforces 679C Bear and Square Grid

链接

传送门

题意

给出$n \times n$的由‘X’和‘.’构成的字符矩阵,求将一块边长为$k$的方形内的字符全都变为‘.’之后,最大的由‘.’组成的连通分量。$(1 \leq k \leq n \leq 500)$

思路

首先dfs求出所有连通分量,然后用滑动窗口进行求解。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
const int maxn = 510;
int n, k, cnt;
int id[maxn][maxn];
int num[maxn * maxn], vis[maxn * maxn];
char g[maxn][maxn];
void dfs(int x, int y) {
id[x][y] = cnt;
++num[cnt];
for (int i = 0; i < 4; ++i) {
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < n && b >= 0 && b < n && g[a][b] == '.' && id[a][b] == 0) {
dfs(a, b);
}
}
}
void add(int x, int y, int clk, int& res) {
if (x >= 0 && x < n && y >= 0 && y < n && g[x][y] == '.' && vis[id[x][y]] != clk) {
vis[id[x][y]] = clk;
res += num[id[x][y]];
}
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 0; i < n; ++i) {
scanf("%s", g[i]);
}
if (n <= k) {
printf("%d\n", n * n);
return 0;
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (g[i][j] == '.' && id[i][j] == 0) {
++cnt;
dfs(i, j);
}
}
}
int ans = 0, clk = 1;
for (int u = 0; u + k <= n; ++u) {
for (int x = 0; x < k; ++x) {
for (int y = 0; y < k; ++y) {
--num[id[u + x][y]];
}
}
for (int l = 0; l + k <= n; ++l) {
int res = k * k;
for (int x = 0; x < k; ++x) {
add(u + x, l - 1, clk, res);
add(u + x, l + k, clk, res);
}
for (int y = 0; y < k; ++y) {
add(u - 1, l + y, clk, res);
add(u + k, l + y, clk, res);
}
++clk;
ans = max(ans, res);
if (l + k != n) {
for (int x = 0; x < k; ++x) {
--num[id[u + x][l + k]];
++num[id[u + x][l]];
}
}
}
for (int x = 0; x < k; ++x) {
for (int y = 0; y < k; ++y) {
++num[id[u + x][n - k + y]];
}
}
}
printf("%d\n", ans);
return 0;
}