題意：一個圖，n個障礙，求聯通塊

?

思路： 圖很大，障礙物很少。把聯通的障礙物塊摳出來，然后暴力。

?

代碼：

?

#include<bits/stdc++.h> using namespace std; #define MEM(a,b) memset(a,b,sizeof(a)) #define bug puts("bug"); #define PB push_back #define MP make_pair #define X first #define Y second typedef unsigned long long ll; typedef pair<int,int> pii; const int maxn=1e5+10; const int mod=1000000007; using namespace std; int t,n,r,c,x,y,ca; pii pp[maxn]; int dir[8][2]={1,0,1,-1,1,1,0,1,0,-1,-1,1,-1,0,-1,-1}; int dd[4][2]={1,0,0,1,0,-1,-1,0}; int mp[205][205],vp[205][205]; vector<ll> ans; set<pii> vis,S; int dfs(int x,int y,int mix,int miy,int mxx,int mxy){int ret=1,tmp;vp[x][y]=1;for(int i=0;i<4;i++){int xx=x+dd[i][0],yy=y+dd[i][1];if(xx<0&&mix!=1) ret=-1;if(yy<0&&miy!=1) ret=-1;if(xx>mxx-mix&&mxx!=r) ret=-1;if(yy>mxy-miy&&mxy!=c) ret=-1;if(xx<0||yy<0||xx>mxx-mix||yy>mxy-miy||vp[xx][yy]||mp[xx][yy])continue;tmp=dfs(xx,yy,mix,miy,mxx,mxy);if(tmp==-1||ret==-1) ret=-1;else ret+=tmp;}return ret; }void bfs(pii P){queue<pii> Q;Q.push(P);vis.insert(P);vector<pii> tp;int mix=1e9+10,miy=1e9+10,mxx=-1,mxy=-1;while(!Q.empty()){pii t=Q.front();mix=min(mix,t.X);miy=min(miy,t.Y);mxx=max(mxx,t.X);mxy=max(mxy,t.Y);tp.PB(t);Q.pop();for(int i=0;i<8;i++){pii nxt=MP(t.X+dir[i][0],t.Y+dir[i][1]);if(!vis.count(nxt)&&S.count(nxt))Q.push(nxt),vis.insert(nxt);}}MEM(mp,0);MEM(vp,0);int ret=0;for(int i=0;i<tp.size();i++) mp[tp[i].X-mix][tp[i].Y-miy]=1;for(int i=0;i<=mxx-mix;i++)for(int j=0;j<=mxy-miy;j++)if(mp[i][j]==0&&vp[i][j]==0&&(ret=dfs(i,j,mix,miy,mxx,mxy))>0) ans.PB(ret);return; } int main(){for(cin>>t,ca=1;ca<=t;ca++){S.clear(),vis.clear(),ans.clear();cin>>r>>c>>n;for(int i=0;i<n;i++) cin>>pp[i].X>>pp[i].Y,S.insert(pp[i]);for(int i=0;i<n;i++) if(vis.count(pp[i])==0) bfs(pp[i]);ll sum=(ll)r*c;for(int i=0;i<ans.size();i++) sum-=ans[i];ans.PB(sum-n);sort(ans.begin(),ans.end());cout<<"Case #"<<ca<<":\n";cout<<ans.size()<<endl;for(int i=0;i<ans.size();i++) cout<<ans[i]<<" \n"[i==ans.size()-1];}return 0; }

轉載于:https://www.cnblogs.com/zhangxianlong/p/10672502.html

總結

以上是生活随笔為你收集整理的hdu 5925 搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。