小z的洞穴之旅 QDUOJ 并查集+连通块

题意

小 z 同学在某个闲暇的周末决定去野外探险一波，结果在丛林深处中误打误撞进入了一个神秘的洞穴，虽然洞穴中光线昏暗，但小 z 凭借其敏锐的眼力立刻辨认出这是一个迷宫状洞穴，并且他还发现了一个现象：该洞穴中时不时会有一个墙块自行坍塌，每个墙体坍塌后其所在单元格即变为空地，其坍塌过程中所产生的尘土也会随之传到该墙体相连的各个空地处，于是他很好奇，对于每一次墙块的坍塌，所产生的尘土会遍及到多大的空白区域？

解题思路

这个题很像《啊哈！算法》中的岛屿问题，但是如果每次有墙倒塌后都进行BFS一次的话会超时，所以这里要先进行预处理，这里预处理是用bfs来扫，把联通的块使用并查集归并到一起（对于二维的数据，需要转化为一维的数据，代码中的getid函数就是干这个的）。之后每次有墙倒塌就查看周围四个位置， 详情见代码实现。

在此也感谢ZYB学长的题解！当时没有尝试做，很忏愧。

代码实现

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<queue>

using namespace std;

const int maxn=5e3+7;

struct note{

	int fa, sum;

}tre[maxn*maxn];

struct node{

	int x, y;

};

int n, m;

char mp[maxn][maxn];

int go[4][2]={1, 0, 0, 1, -1, 0, 0, -1};

queue<node> q;

inline int getid(int x, int y)// getid()将二维点(x,y)映射为一维的数值

{

	return (x-1)*m + y;

 }

int find(int x) //寻找父节点，并且进行路径压缩

{

	if(tre[x].fa==x) return x;

	else return tre[x].fa = find(tre[x].fa);

}

void merge(int u, int v) //这里合并时按照各自集合中点的个数来进行合并

{

	u=find(u);

	v=find(v);

	if(u==v) return ;

	if(tre[u].sum >= tre[v].sum)

	{

		tre[v].fa=u;

		tre[u].sum+=tre[v].sum;

	}

	else {

		tre[u].fa=v;

		tre[v].sum+=tre[u].sum;

	}

}

void bfs(int x, int y, int rt) //预处理中的一部分

{

	while(!q.empty()) q.pop() ;

	node h={x, y}, tmp;

	int tx, ty, id;

	q.push(h);

	while(!q.empty())

	{

		h=q.front();

		q.pop() ;

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

		{

			tx=h.x+go[i][0];

			ty=h.y+go[i][1];

			if(tx<=0 || tx>n || ty<=0 || ty>m || mp[tx][ty]=='#')

				continue;

			id=getid(tx, ty);

			if(tx==x && ty==y || tre[id].fa!=id) continue;

			merge(rt, id);

			tmp.x=tx;

			tmp.y=ty;

			q.push(tmp);

		}

	}

}

void init() //预处理的主程序

{

	int id;

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

	for(int j=1; j<=m; j++)

	{

		id=getid(i, j);

		tre[id].fa=id; //默认父节点都是自己

		tre[id].sum=1;//默认个数都是1

	}

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

	for(int j=1; j<=m; j++)

	{

		id=getid(i, j);

        // fa[tmp]!=tmp即表示该块已被遍历过

		if(mp[i][j]=='#' || tre[id].fa != id) continue;

		bfs(i, j, id);

	}

}

int main()

{

	int q, x, y, tx, ty, id, tmp;

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

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

		scanf("%s", mp[i]+1);

	init();

	scanf("%d", &q);

	while(q--)

	{

		scanf("%d%d", &x, &y);

		id=getid(x, y);

        //尝试将(x,y)点与周围上下左右四个区域合并

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

		{

			tx=x+go[i][0];

			ty=y+go[i][1];

			if(tx<=0 || tx>n || ty<=0 || ty>m || mp[tx][ty]=='#')

				continue;

			tmp=getid(tx, ty);

			merge(id, tmp);

		}

		mp[x][y]='.'; //最后还需要维护原始的mp[][]

		printf("%d\n", tre[find(id)].sum); //返回当前点(x,y)所在的连通块的大小

	}

	return 0;

}