社区讨论

求教,并查集+DFS怎么改

P114101迷宫参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mi7xakvk
此快照首次捕获于
2025/11/21 05:07
4 个月前
此快照最后确认于
2025/11/21 05:07
4 个月前
查看原帖
CPP
#include <cstdio>
#include <utility>
#include <map>
#define pii std::pair<int,int>
#define mkpii(a,b) std::make_pair((a),(b))
const int dx[4]= {0,0,1,-1},dy[4]= {1,-1,0,0};
int n,maps[1005][1005];
bool done[1005][1005];
std::map<pii,pii>f;
std::map<pii,int>value;
pii find(pii a)
{
	return f[a]==a?a:f[a]=find(f[a]);
}
void hb(pii a,pii b)
{
	pii fa=find(a),fb=find(b);
	if (fa!=fb)	f[fb]=fa;
	return;
}
void dfs(int x,int y)
{
	done[x][y]=true;
	for (int i=0; i<4; i++)
		if (!done[x+dx[i]][y+dy[i]]&&maps[x][y]+maps[x+dx[i]][y+dy[i]]==1)
			hb(mkpii(x,y),mkpii(x+dx[i],y+dy[i])),
			dfs(x+dx[i],y+dy[i]);
}
int main()
{
	int a,b,m,sum;
	scanf("%d%d",&n,&m);
	int sss[n+2][n+2];
	for (int i=1; i<=n; ++i)
		for (int j=1; j<=n; ++j)
			scanf("%1d",&sss[i][j]),
			f[mkpii(i,j)]=mkpii(i,j);
	while (m--)
	{
		sum=0;
		for (int i=1; i<=n; ++i)
			for (int j=1; j<=n; ++j)
				done[i][j]=false,
				           maps[i][j]=sss[i][j];
		scanf("%d%d",&a,&b);
		dfs(a,b);
		if (find(mkpii(a,b))==mkpii(a,b))
		{
			for (int i=1; i<=n; ++i)
				for (int j=1; j<=n; ++j)
					if (done[i][j])
						++sum;
			value[find(mkpii(a,b))]=sum;
		}
		printf("%d\n",value[find(mkpii(a,b))]);
	}
	return 0;
}

回复

4 条回复,欢迎继续交流。

正在加载回复...