自动搬运

查看原文

来自洛谷，原作者为

	Tiffake The King Or The Fool|穷途末路的旷野|食无足怒无故贪不知足，岂无妒惰无睹色空前路

搬运于2025-08-24 22:34:31，当前版本为作者最后更新于2025-01-14 22:21:02，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意

简单来说，就是让你构造一种用一笔画铺满左右两个区域的方案，数据范围较小。

思路

乍看之下似乎有点难，因为很难保证询问的路径不会互相重复。可以考虑一种类似于“贪吃蛇”的套路——不断地走 S 型弯路，直到首尾相接，如下图。

对于横向拓展，每次向前两格一定没问题，因为这样正好可以向下之后再回来，竖向拓展同理。
但是判断要不要继续沿当前方向拓展是一个难点。可以考虑判断如果继续拓展，会不会走到对面区域。如果会，那就向下拓展；否则，尽可能地向对面拓展。
代码实现如下：

inline bool chk(int x,int y){
	return !a[x][y-1]||a[x][y];//判断是否走到对面去了
}
//先构造地图，方便后续操作
x=1,y=1;while(a[x][y]&&a[x+1][y])x+=2;//开始点一定不能在路径上
for(sx=x,sy=y;x<=n;x++,y--){
	mp[x-1][y++]='d';
	if(x==sx&&chk(x,y))mp[x][y-1]='r',y++;
	while(y<m&&x&1&&chk(x,y)&&chk(x,y+1))
		mp[x][y-1]=mp[x][y]='r',y+=2;//能走就走，记得一次走两步
}

这样，我们就可以得到左边区域紧贴路径的走法了。
然后，把左区域的剩下区域填满就行了。由于我们之前每次都拓展了两格，因此直接走 S 型弯路就行了，代码如下：

for(x--,y--;y>=1;y--){
	mp[x--][y+1]='l';
	while(!mp[x][y])mp[x+1][y]='u',x--;//向上走
	x++,mp[x][y]='l',y--;
	while(x<=n&&!mp[x][y]){//向下走
		if(!mp[x-1][y])mp[x-1][y]='d';
		x++;
	}
	x--;
}
mp[tx=sx+1][ty=sy]='u';//记得特判最后一格

右边的地图构造方式也和左边差不多，不再过多赘述。

但是这样跑一遍只能找出一个点，还需要再反着跑一遍才能找到另一个点，因此考虑建反图：

inline void go(int&x,int&y,char c){
	switch(c){
		case 'u':x--;break;
		case 'd':x++;break;
		case 'l':y--;break;
		case 'r':y++;break;
	}
}
inline char rgo(char x){//取反某个方向
	switch(x){
		case 'u':return 'd';
		case 'd':return 'u';
		case 'l':return 'r';
		case 'r':return 'l';
	}
	return 0;
}
inline void Getrevmap(){
	x=sx,y=sy;
	for(int lx=x,ly=y;lx!=tx||ly!=ty;lx=x,ly=y)
		go(x,y,mp[x][y]),rmp[x][y]=rgo(mp[lx][ly]);
	//先走一步，再把当前位置的方向改为走到的位置的反方向
	go(x,y,mp[x][y]),rmp[x][y]=rgo(mp[tx][ty]);//要特判最后一格
}

最后按照造好的地图模拟查询即可，给出 main 函数的代码：

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<n+m;i++)cin>>x>>y,a[x][y]=1;
	Getlmap(),v.push_back({sx,sy}),r.push_back({sx+1,sy});
	for(x=sx,y=sy;!ask(x,y);v.push_back({x,y}))go(x,y,mp[x][y]);
	Getrevmap();
	for(x=sx+1,y=sy;!ask(x,y);r.push_back({x,y}))go(x,y,rmp[x][y]);
	reverse(r.begin(),r.end());
	while(v.size())cout<<v.back().fst<<' '<<v.back().snd<<'\n',v.pop_back();
	while(r.size())cout<<r.back().fst<<' '<<r.back().snd<<'\n',r.pop_back();
	cout<<"-1 -1"<<endl;
	memset(mp,0,sizeof mp),memset(rmp,0,sizeof rmp);//记得清空地图
	Getrmap(),v.push_back({sx,sy}),r.push_back({sx-1,sy});
	for(x=sx,y=sy;!ask(x,y);v.push_back({x,y}))go(x,y,mp[x][y]);
	Getrevmap();
	for(x=sx-1,y=sy;!ask(x,y);r.push_back({x,y}))go(x,y,rmp[x][y]);
	reverse(r.begin(),r.end());
	while(v.size())cout<<v.back().fst<<' '<<v.back().snd<<'\n',v.pop_back();
	while(r.size())cout<<r.back().fst<<' '<<r.back().snd<<'\n',r.pop_back();
	cout<<"-1 -1"<<endl;
	return 0;
}