题目描述
※ 简单版与困难版的唯一区别是 n,m,q 的数据范围
给一个n×m 的网格,每个格子里有一个数字,非 00 即 11,行从上往下依次编号为 1, 2⋯,n,列从左往右依次编号为 1,2,⋯,m。
给 qq 次操作,每次给定一个以(x1,y1) 为左上角,(x2,y2) 为右下角的矩形内所有格子里的数字都变成 1。问每次操作之后,所有数字为 1 的格子构成的四连通块的个数。
若不懂四连通块的定义可见最底下的提示。
输入描述
输入第一行两个整数 n,m(1≤n,m≤1000),表示网格大小。
接下来 n 行,每行一个长为 m 的 01 串,表示初始网格。
接下来一行一个整数 q (1≤q≤30000),表示操作个数。
接下来 qq 行,每行四个整数 x1,y1,x2,y2 (1≤x1≤x2≤n,1≤y1≤y2≤m) 表示把以 (x1,y1) 为左上角,(x2,y2) 为右下角的矩形中的元素都变成 1。
输出描述
输出共 qq 行,每行一个整数,表示每次操作后含有数字 1 的格子构成的四连通块的个数。
解题思路:维护两个并查集, 对于每行开一个有关连续1的并查集,指向最右边的1。对于整体开一个并查集统计联通块。
#include <bits/stdc++.h> using namespace std; const int maxn=1e6+5; const int N=1005; int n,m,ans,cnt; char s[N][N]; int id[N][N],p[maxn],fa[N][N]; int dir[4][2]={0,1,0,-1,1,0,-1,0}; int find(int x) {return x==p[x]?x:p[x]=find(p[x]);} int ff(int x,int y) {return y==fa[x][y]?y:fa[x][y]=ff(x,fa[x][y]);} void dfs(int x,int y) { ans++;id[x][y]=++cnt;p[cnt]=cnt; int rx=ff(x,y),ry=ff(x,y+1); if(rx!=ry) fa[x][rx]=ry; for(int i=0;i<4;i++){ int xx=x+dir[i][0],yy=y+dir[i][1]; if(xx<1||xx>n||yy<1||yy>m||id[xx][yy]==0) continue; rx=find(id[x][y]),ry=find(id[xx][yy]); if(rx!=ry) p[rx]=ry,ans--; } } int main() { int q; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m+1;j++) fa[i][j]=j; for(int i=1;i<=n;i++){ scanf("%s",s[i]+1); for(int j=1;j<=m;j++) if(s[i][j]=='1') dfs(i,j); } scanf("%d",&q); while(q--){ int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); for(int i=x1;i<=x2;i++){ for(int j=ff(i,y1);j<=y2;j=ff(i,y1)) dfs(i,j); } printf("%d\n",ans); } }