自动搬运

查看原文

来自洛谷，原作者为

	Leap_Frog 是啊……你就是那只鬼了……所以被你碰到以后，就轮到我变成鬼了

搬运于2025-08-24 21:23:30，当前版本为作者最后更新于2019-03-27 15:48:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P1299切孔机（题解）

PS:
人生中的第一道黑题。
发一个题解纪念一下。

解题算法：

• 离散化
• 广度优先搜索,bfs

解题思路：

1. 首先先把读入的x,y离散化
2. 把所有的切痕记录下来
3. bfs把孔外的格子找出来
4. 数有几个格子。（一个图中有几个连通块）

我的代码：

• xx,yy:表示方向。
• point:表示点。
  • number:第几次切
  • x,y:切的点的坐标
• picture:记录切痕
  • can_go:一个点可以不可以向上下左右走(0:上,1:下,2:左:右)
  • visit:一个点是不是孔中的点(0:不是,1:是)
• cmpx,cmpy:离散化时用
• cmp:切的次数从小到大，第一个切点尽量左上
• ready:读入
• lisan:离散化
• build_wall:把所有切痕记录下来（2）
• cut_paper:剪纸，把孔外的格子记录下来（3）
• count_hole:数有几个洞（4）

上代码

#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;
}