1 条题解
-
0
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll xx[4]={-1,1,0,0},yy[4]={0,0,-1,1}; struct point { ll number,x,y; point() {} point(ll a,ll b):x(a),y(b) {} }; struct picture { bool can_go[4],visit; picture() { can_go[0]=can_go[1]=can_go[2]=can_go[3]=1; visit=1; } }; ll n; point a[205]; picture b[205][205]; inline bool cmpx(point a,point b) { return a.x<b.x; } inline bool cmpy(point a,point b) { return a.y<b.y; } inline bool cmp(point a,point b) { if(a.number!=b.number) return a.number<b.number; if(a.x!=b.x) return a.x<b.x; return a.y<b.y; } inline void ready() { scanf("%lld",&n); for(int i=1;i<=n*2;i++) { a[i].number=(i+1)/2; scanf("%lld%lld",&a[i].x,&a[i].y); } } inline void lisan() { ll now,u; now=-10000005; u=0; sort(a+1,a+n*2+1,cmpx); for(ll i=1;i<=n*2;i++) { if(a[i].x!=now) { now=a[i].x; u++; a[i].x=u; } else a[i].x=u; } now=-10000005; u=0; sort(a+1,a+n*2+1,cmpy); for(ll i=1;i<=n*2;i++) { if(a[i].y!=now) { now=a[i].y; u++; a[i].y=u; } else a[i].y=u; } } inline void build_wall() { sort(a+1,a+n*2+1,cmp); for(ll i=1;i<=n;i++) { point s=a[i*2-1],e=a[i*2]; for(ll j=s.x+1;j<=e.x;j++) { b[j][s.y].can_go[3]=0; b[j][s.y+1].can_go[2]=0; } for(ll j=s.y+1;j<=e.y;j++) { b[s.x][j].can_go[1]=0; b[s.x+1][j].can_go[0]=0; } } } inline void cut_paper() { queue<point>q; q.push(point(0,0)); while(!q.empty()) { point now=q.front(); q.pop(); for(int i=0;i<4;i++) { ll x=now.x+xx[i],y=now.y+yy[i]; if(x<0||x>200||y<0||y>200) continue; if(!b[x][y].visit) continue; if(!b[now.x][now.y].can_go[i]) continue; b[x][y].visit=0; q.push(point(x,y)); } } } inline void bfs(ll dx,ll dy) { queue<point>q; b[dx][dy].visit=0; q.push(point(dx,dy)); while(!q.empty()) { point now=q.front(); q.pop(); for(int i=0;i<4;i++) { ll x=now.x+xx[i],y=now.y+yy[i]; if(x<0||x>200||y<0||y>200) continue; if(!b[x][y].visit) continue; b[x][y].visit=0; q.push(point(x,y)); } } } inline ll count_hole() { ll ans=0; for(ll i=0;i<=200;i++) for(ll j=0;j<=200;j++) { if(!b[i][j].visit) continue; ans++; bfs(i,j); } return ans; } int main() { ready(); lisan(); build_wall(); cut_paper(); ll ans=count_hole(); printf("%lld\n",ans); return 0; }
- 1
信息
- ID
- 300
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者