自动搬运

查看原文

来自洛谷，原作者为

	Math_rad_round 旋转卡壳有2^4种读法，你知道吗？||NOIP退役苕皮

搬运于2025-08-24 22:29:19，当前版本为作者最后更新于2022-10-09 12:30:04，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

鉴于 $x,y$ 范围很小，我们这道题可以直接先把每一条线段覆盖到的点打上标记 $a$。

然后从点 $T$ dfs（bfs），只走标记 $a$ 的点，同时给遍历到的点打上标记 $b$。

在 bfs 的过程中计算上下左右四至点，也就是路途中最大/最小的 $X/Y$ 坐标。

最后输出上一步求出的 $X/Y$ 坐标范围内的矩形，有标记 $b$ 的才输出 '#'

然而，这种做法有一个致命缺陷：如下图样例所示：

左图区分开了四条线段
右图是完成第一步打标记A的点
****  AAAA
#..#  A..A
#..#  A..A
****  AAAA                   

4
1 1 4 1
1 2 1 3
1 4 4 4
4 2 4 3
1 1

四条线段都不交，然而直接 dfs (1,1) 就会遍历上整张图。因此，面对这个困难，我们选择拆点，读入时将 $X,Y$ 坐标翻倍；

*******
.......
#.....#
#.....#
#.....#
.......
*******

容易发现，现在四条线段都互不相邻了。

最后一步输出时只需输出横纵坐标均为偶数的点即可。

代码如下，本题建议评绿。

#include<iostream>
using namespace std;
int s[1000][1000];
int fx[4]={0,1,0,-1},fy[4]={1,0,-1,0};
int lx=1e9,rx,uy,dy=1e9;
void dfs(int x,int y){
	if(s[x][y]!=1)return;
	s[x][y]=2;lx=min(lx,x);rx=max(rx,x);uy=max(uy,y);dy=min(dy,y);
	for(int f=0;f<4;f++){
		dfs(x+fx[f],y+fy[f]);
	}
}
int main(){
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		int a1,a2,a3,a4;cin>>a1>>a2>>a3>>a4;
		if(a1>a3)swap(a1,a3);if(a2>a4)swap(a2,a4);
		a1*=2;a2*=2;a3*=2;a4*=2;
		for(int a=a1;a<=a3;a++){
			for(int b=a2;b<=a4;b++){
				s[a+1][b+1]=1;
			}
		}
	}
	int x,y;cin>>x>>y;x*=2;y*=2;x++;y++;
	dfs(x,y);
	if(rx==0)return 0;
	for(int j=uy;j>=dy;j-=2){
		for(int i=lx;i<=rx;i+=2){
			if(s[i][j]==2)cout<<"#";else cout<<"."; 
		}cout<<endl;
	}
}