题解 - 汪哥图 (wang.cpp)

问题描述

给定一个 $n$ 行 $m$ 列的网格图，每个格子的颜色是蓝色、白色中的一种。白色的格子是障碍点。对于 $2$ 个有公共边的蓝色格子，它们之间是连通的。保证任意 $2$ 个蓝色格子间最多只有 $1$ 条不经过白色格子的路径。现给出 $Q$ 个矩形区域，对每个矩形区域求出对蓝色格子来说的连通块个数（不能经过白色格子和矩形区域外的格子）。

数据范围： $n,m \leq 2000, Q \leq 200000$

样例输入

3 4 4
1101
0110
1101
1 1 3 4
1 1 3 1
2 2 3 4
1 2 2 4

样例输出

3
2
2
2

题解

我们注意：题目保证任意 $2$ 个蓝色格子间最多只有 $1$ 条不经过白色格子的路径。也就是说没有方块咯。那么可以把这些东西理解成一堆树，树的边为点减一，看到这里应该很容易想出有多少棵树。

所以有如下性质：

\[连通块数 = 1的点数 - 1之间的边数\]

维护三个前缀和，记录点的数量，上下相连的数量和左右相连的数量。

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define y1 y3
#define y0 y4
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
const int N = 2010;
int n, m, q;
bool mp[N][N];
int c[N][N], v1[N][N], v2[N][N];
int main()
{
  scanf("%d%d%d", &n, &m, &q);
  char ch[2010];
  for(int i = 1; i <= n; i++) {
    scanf("%s", ch);
    for(int j = 1; j <= m; j++) {
      mp[i][j] = ch[j - 1] - '0';
      c[i][j] = c[i - 1][j] + c[i][j - 1] - c[i - 1][j - 1] + mp[i][j];
      v1[i][j] = v1[i - 1][j] + v1[i][j - 1] - v1[i - 1][j - 1];
      v2[i][j] = v2[i - 1][j] + v2[i][j - 1] - v2[i - 1][j - 1];
      if(mp[i][j] == mp[i - 1][j] && mp[i][j] == 1) v1[i][j]++;//上下
      if(mp[i][j] == mp[i][j - 1] && mp[i][j] == 1) v2[i][j]++;//左右
    }
  }
  getchar();
  int x1, x2, y1, y2;
  while(q--) {
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    int ans = c[x2][y2] - c[x1 - 1][y2] - c[x2][y1 - 1] + c[x1 - 1][y1 - 1];
    x1++;
    ans -= v1[x2][y2] - v1[x1 - 1][y2] - v1[x2][y1 - 1] + v1[x1 - 1][y1 - 1];
    x1--, y1++;
    ans -= v2[x2][y2] - v2[x1 - 1][y2] - v2[x2][y1 - 1] + v2[x1 - 1][y1 - 1];
    printf("%d\n", ans);
  }
  return 0;
}