1 条题解

  • 0
    @ 2022-6-19 21:51:11
    #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
    上传者