本文主要是介绍P3820 小D的地下温泉，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
*原题链接*
这道题前前后后调了两个多小时，终于过了，细节是真的多，我几乎把所有坑都踩过了，就在此总结一下。
对于此题做法并不难想，维护集合大小和连通性，很容易想到并查集来维护，我们把二维降到一维，先预处理出每块温泉的大小，再处理操作。1操作很容易，对于2操作，如果该点是温泉，由于题中明确说将温泉变为土时不会将一个区域分割，所以直接将其所在连通块大小减1；如果是土块，需要新建一个编号表示这块地。接下来诸多我踩过的坑见代码注释
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;//原矩阵n*m<=1e6,再加上1e6次操作，所以空间大小开2e6int n,m,q,fa[N],sz[N],c[N],tot,newpos[N];
char ch,mp[N];int cal(int i,int j){//二维降到一维，而我写成(i-1)*n+1return (i-1)*m+j;
}int find(int x){if(x!=fa[x]) fa[x]=find(fa[x]);return fa[x];
}void unionn(int a,int b){//合并操作最好单独写一个函数，不然很容易写乱int x=find(a),y=find(b);if(x==y) return;sz[x]+=sz[y],fa[y]=x;
}void init(){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(mp[cal(i,j)]=='*'){sz[cal(i,j)]=0;continue;}//如果是土块就重置它的sz，并continueif(i-1>=1&&mp[cal(i-1,j)]=='.') unionn(cal(i,j),cal(i-1,j));if(j-1>=1&&mp[cal(i,j-1)]=='.') unionn(cal(i,j),cal(i,j-1));}}
}void solve(int pos,int x,int y){//给该地新分配一个编号，并初始化newpos[pos]=tot++,mp[pos]='.',fa[newpos[pos]]=newpos[pos],sz[newpos[pos]]=1;if(x-1>=1&&mp[cal(x-1,y)]=='.') unionn(newpos[pos],newpos[cal(x-1,y)]);if(y-1>=1&&mp[cal(x,y-1)]=='.') unionn(newpos[pos],newpos[cal(x,y-1)]);if(x+1<=n&&mp[cal(x+1,y)]=='.') unionn(newpos[pos],newpos[cal(x+1,y)]);if(y+1<=m&&mp[cal(x,y+1)]=='.') unionn(newpos[pos],newpos[cal(x,y+1)]);
}int main(){ios::sync_with_stdio(false);cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>ch;mp[cal(i,j)]=ch;}}for(int i=1;i<N;i++) newpos[i]=i,fa[i]=i,sz[i]=1;tot=cal(n,m)+1;init();cin>>q;while(q--){int opt,w;cin>>opt>>w;//接下来的操作要分清newpos数组和pos，千万不要搞混if(opt==1){int res=0,ans=1;//ans初值设为1，不要设为0，可能有都是土块的情况。for(int i=1;i<=w;i++){int x,y;cin>>x>>y;int pos=cal(x,y);if(sz[find(newpos[pos])]>res&&mp[pos]=='.') res=sz[find(newpos[pos])],ans=i;}cout<<ans<<endl;}else{for(int i=1;i<=w;i++){int x,y;cin>>x>>y;int pos=cal(x,y);if(mp[pos]=='.') mp[pos]='*',sz[find(newpos[pos])]--;else solve(pos,x,y);}}}return 0;
}这篇关于P3820 小D的地下温泉的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
