Codeforces 679C Bear and Square Grid

发表于 分类于 Disqus：

链接

传送门

题意

给出\(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;
}
相关文章