Comet OJ - Contest #13 「佛御石之钵 -不碎的意志-」(困难版) 并查集

题意

给一个$ n \times m$ 的网格，每个格子里有一个数字，非 $0$ 即 $1$，行从上往下依次编号为 $1, 2, \cdots, n$，列从左往右依次编号为 $1, 2, \cdots, m$。

给 $q$ 次操作，每次给定一个以 $(x_1,y_1)$ 为左上角，$(x_2,y_2)$ 为右下角的矩形内所有格子里的数字都变成 $1$。问每次操作之后，所有数字为 $1$的格子构成的四连通块的个数。

$1<=n,m<=1000$

$1<=q<=30000$

分析

搬运官方题解..

Code

#include<bits/stdc++.h>

#define fi first

#define se second

#define lson l,mid,p<<1

#define rson mid+1,r,p<<1|1

#define pb push_back

#define ll long long

using namespace std;

const int inf=1e9;

const int mod=1e9+7;

const int maxn=1e6+10;

int n,m,q;

char s[1010][1010];

int id[1010][1010],f[maxn];

int xx[]={0,0,1,-1};

int yy[]={1,-1,0,0};

int g[1010][1010];

int ans,tot;

int find(int k){

	if(k==f[k]) return k;

	return f[k]=find(f[k]);

}

int ff(int x,int k){

	if(k==g[x][k]) return k;

	return g[x][k]=ff(x,g[x][k]);

}

void dfs(int x,int y){

	++ans,id[x][y]=++tot;f[tot]=tot;

	int rx=ff(x,y),ry=ff(x,y+1);

	if(rx!=ry) g[x][rx]=ry;

	for(int i=0;i<4;i++){

		int dx=x+xx[i];

		int dy=y+yy[i];

		if(dx<1||dx>n||dy<1||dy>m||!id[dx][dy]) continue;

		int rx=find(id[x][y]),ry=find(id[dx][dy]);

		if(rx!=ry) f[rx]=ry,--ans;

	}

}

int main(){

	//ios::sync_with_stdio(false);

	//freopen("in","r",stdin);

	scanf("%d%d",&n,&m);

	int tot=0;

	for(int i=1;i<=n;i++)

	for(int j=1;j<=m+1;j++) g[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);

	}

	return 0;

}

巴特西

Comet OJ - Contest #13 「佛御石之钵 -不碎的意志-」(困难版) 并查集

题意

分析

Code

最新文章

热门文章