题意
给出一张$n times m$的网格，其中$1$为蓝点，$2$为白点。
$q$次询问，每次询问一个子矩阵内蓝点形成的联通块的数量
保证任意联通块内的任意蓝点之间均只有一条路径可达
sol
mdzz不好好读题目还想做题，。。
题目中说“联通块内的任意点都只有一条路径可达”，不难推断出这是一棵树
因此 联通块个数 = 蓝点的数量 – 蓝点间边的数量
考虑用前缀和维护，点的数量好处理，但是这个边的数量有点麻烦
反正我用一个数组是搞不出来，因为无法判断左右的方向。。
那就行列分别记录一下就可以了。
#include<cstdio> #include<iostream> #include<cstring> #define ll long long using namespace std; const int maxn = 2001; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, m, q; char s[maxn][maxn]; int p[maxn][maxn], r[maxn][maxn], l[maxn][maxn]; int getp(int x, int y) { if(x == 0 || y == 0) return 0; return p[x - 1][y] + p[x][y - 1] - p[x - 1][y - 1]; } int getr(int x, int y) { if(x == 0 || y == 0) return 0; return r[x - 1][y] + r[x][y - 1] - r[x - 1][y - 1]; } int getl(int x, int y) { if(x == 0 || y == 0) return 0; return l[x - 1][y] + l[x][y - 1] - l[x - 1][y - 1]; } main() { n = read(); m = read(); q = read(); for(int i = 1; i <= n; i++) { scanf("%s", s[i] + 1); for(int j = 1; j <= m; j++) { p[i][j] = getp(i, j); r[i][j] = getr(i, j); l[i][j] = getl(i, j); if(s[i][j] == '1') l[i][j] += (s[i - 1][j] == '1'), r[i][j] += (s[i][j - 1] == '1'), p[i][j]++; } } /*for(int i = 1; i <= n; i++, puts("")) for(int j = 1; j <= m; j++) printf("%d ", l[i][j]);*/ while(q--) { int x1 = read(), y1 = read(), x2 = read(), y2 = read(); // printf("%d %d %d %dn", getp(x2, y2), getp(x1 - 1, y2), getp(x2, y1 - 1), getp(x1 - 1, y1 - 1)); int ans1 = p[x2][y2] - p[x1 - 1][y2] - p[x2][y1 - 1] + p[x1 - 1][y1 - 1]; int ans2 = r[x2][y2] - r[x1 - 1][y2] - r[x2][y1] + r[x1 - 1][y1]; int ans3 = l[x2][y2] - l[x2][y1 - 1] - l[x1][y2] + l[x1][y1 - 1]; cout << ans1 - ans2 - ans3 << endl; } return 0; } /* */
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/607772.html