正題

---

大意

有n個(gè)正方形，求塊數(shù)。

---

解題思路

用并查集求塊數(shù)

---

代碼

#include<cstdio> #include<algorithm> using namespace std; int i,lt[7001],x1[7001],y1[7001],x2[7001],y2[7001],n,s; int father(int x) {if (lt[x]!=x) lt[x]=father(lt[x]);return lt[x]; }//找祖先 void unionn(int x,int y) {int fa=father(x);int fb=father(y);if (fa!=fb) lt[fa]=fb; }//連接 bool ok(int r1x1,int r1y1,int r1x2,int r1y2,int r2x1,int r2y1,int r2x2,int r2y2) {if (r1x2<r2x1 || r2x2<r1x1) return false;if (r1y2<r2y1 || r2y2<r1y1) return false;if ((r1x1==r2x2 || r1x2==r2x1)&&(r1y1==r2y2 || r1y2==r2y1)) return false;else return true; }//確定兩個(gè)方塊是否重合 int main() {scanf("%d",&n);for (int i=1;i<=n;i++) lt[i]=i;for (int i=1;i<=n;i++){scanf("%d%d%d%d",&x1[i],&y1[i],&x2[i],&y2[i]);for (int j=1;j<i;j++){if (father(i)!=father(j))if (ok(x1[j],y1[j],x2[j],y2[j],x1[i],y1[i],x2[i],y2[i])){unionn(i,j);//連接}}}for (int i=1;i<=n;i++) if (father(i)==i) s++;//統(tǒng)計(jì)printf("%d",s); } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的ssl1222-矩形【图论，并查集】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。