自动搬运

查看原文

来自洛谷，原作者为

	_xiaxii 原名 HPY_xiaxii||Uplifting Trance Forever!

搬运于2025-08-24 22:27:26，当前版本为作者最后更新于2022-11-29 15:36:43，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

P7185 [CRCI2008-2009] CIJEVI

还没有题解，赶紧水一篇。

$Wrote\space on\space 2022/11/29$

$Updated\space on\space 2023/11/12$ 被 $Hack$ 力。

题意理解

输入一张管道的图，求缺失的一块管道的信息。

这是一道模拟题，给出一种有趣繁琐的做法。题目给出了起点终点，且只有一块管道是缺失的。我们其实可以沿着整个管道走一遍。考虑到地图和管道的种类不是很多，可以采用枚举的方法。首先我们使用一个 map 来表示这个方向是否可走。定义一个函数 f(int x,int y,int d) 来走路径，其中 $x$ 与 $y$ 来表示当前的坐标，$d$ 表示方向。第一次调用 f(x,y,d) 函数我们通过第一个空格可以找到缺少的管道的坐标。然后再进行 $7$ 次的对管道类型的枚举，我们就可以开始走了。

首先在起点处找第一个管道，且只有一条，因为题目说明了该计划将没有冗余构建块，即在添加丢失的块之后必须使用计划中的所有块，否则管道的另一边会被堵死。如果检测到撞到管道壁或者当前在空格的位置，即无法继续往后走下去了，这种填法就是错误的。

我们定义向上为 $1$，向右为 $2$，向下为 $3$，向左为 $4$。方向的变换之间有一对一的关系，变换稍微有点复杂，要注意不要写错。

• 若当前管道为 +，则方向不改变。
• 若当前管道为 -，则方向不改变。
• 若当前管道为 |，则方向不改变。
• 若当前管道为 1，则方向 $1$ 变为 $2$，$4$ 变为 $3$。
• 若当前管道为 2，则方向 $3$ 变为 $2$，$4$ 变为 $1$。
• 若当前管道为 3，则方向 $3$ 变为 $4$，$2$ 变为 $1$。
• 若当前管道为 4，则方向 $2$ 变为 $3$，$1$ 变为 $4$。

枚举要把 + 的情况放在最后，因为这个管道会影响到 - 和 | 的情况。

看似已经没有问题了，交上去，错了两个点。

仔细思考，就会发现一个问题，比如说如下的结构：

$$\begin{matrix} . &.&1&-&4\\ . & .&|&.&|\\ M & -&.&-&3\\ .&.&|&.&.\\ .&.&Z&.&. \end{matrix}$$

根据题目所说的该计划将没有冗余构建块，即在添加丢失的块之后必须使用计划中的所有块，我们很容易看出来在 $(3,3)$ 的位置应该填 +，然而程序填了 4。

这个问题很好解决，用一个 book 数组标记每个管道是否用过就行了。

Hack

时隔一年的Hack。

考虑这样的数据：

1 3
M.Z

运行之后发现什么也没输出。仔细看看代码会发现，如果入口处没有任何管道，则 fixx 和 fixy 中都不会有值。解决办法是直接在入口周围的空地上枚举管道直到成功。

代码

#include <bits/stdc++.h>
using namespace std;

int r,c;
int sx,sy,fx,fy,dir,fixx,fixy,block=6;
int book[50][50];//记录是否走过
char e[30][30];
bool flag=true, hack = false;

//用几个map来标记当前是否可走

map<char,int> _left;
map<char,int> up;
map<char,int> _right;
map<char,int> down;

int nt[4][2]={{-1,0},{0,1},{1,0},{0,-1}};//位置的变化量
char bl[8]={'+','-','|','1','2','3','4'};//记录每种管道

void check()//找到第一步的方向
{
	if(up[e[sx-1][sy]])
	{
		dir=1;
	}
	if(_right[e[sx][sy+1]])
	{
		dir=2;
	}
	if(down[e[sx+1][sy]])
	{
		dir=3;
	}
	if(_left[e[sx][sy-1]])
	{
		dir=4;
	}
}

bool k(int x,int y,int d)//判断这一步是否可走
{
	x+=nt[d-1][0];
	y+=nt[d-1][1];
	if(d==1)
	{
		return up[e[x][y]];
	}
	if(d==2)
	{
		return _right[e[x][y]];
	}
	if(d==3)
	{
		return down[e[x][y]];
	}
	if(d==4)
	{
		return _left[e[x][y]];
	}
}

void f(int x,int y,int d)
{
	book[x][y]=1;
	
    //对方向的更新
    
	int p=d;
	if(e[x][y]==bl[3])
	{
		p=d==1?2:3; 
	}
	if(e[x][y]==bl[4])
	{
		p=d==3?2:1; 
	}
	if(e[x][y]==bl[5])
	{
		p=d==3?4:1;
	}
	if(e[x][y]==bl[6])
	{
		p=d==1?4:3;
	}
    
    //模拟每种管道的走法
	
	if(e[x][y]==bl[0]&&((d==1&&k(x,y,d))||(d==2&&k(x,y,d))||(d==3&&k(x,y,d))||(d==4&&k(x,y,d))))
	{
		f(x+nt[d-1][0],y+nt[d-1][1],d);
	}
	else if(e[x][y]==bl[1]&&((d==2&&k(x,y,d))||(d==4&&k(x,y,d))))
	{
		f(x,y+nt[d-1][1],d);
	}
	else if(e[x][y]==bl[2]&&((d==1&&k(x,y,d))||(d==3&&k(x,y,d))))
	{
		f(x+nt[d-1][0],y,d);
	}
	else if(e[x][y]==bl[3]&&((d==1&&k(x,y,2))||(d==4&&k(x,y,3))))
	{
		p=d==1?2:3; 
		f(x+nt[p-1][0],y+nt[p-1][1],p);
	}
	else if(e[x][y]==bl[4]&&((d==3&&k(x,y,2))||(d==4&&k(x,y,1))))
	{
		p=d==3?2:1; 
		f(x+nt[p-1][0],y+nt[p-1][1],d==3?2:1);
	}
	else if(e[x][y]==bl[5]&&((d==2&&k(x,y,1))||(d==3&&k(x,y,4))))
	{
		p=d==3?4:1; 
		f(x+nt[p-1][0],y+nt[p-1][1],d==3?4:1);
	}
	else if(e[x][y]==bl[6]&&((d==2&&k(x,y,3))||(d==1&&k(x,y,4))))
	{
		p=d==1?4:3; 
		f(x+nt[p-1][0],y+nt[p-1][1],d==1?4:3);
	}
	else if(x+nt[p-1][0]==fx&&y+nt[p-1][1]==fy)//如果走到了终点
	{
		
	    bool flag2=true;
		for(int i=1;i<=r;i++)
		{
			for(int j=1;j<=c;j++)
			{
				if(e[i][j]!='.'&&e[i][j]!='M'&&e[i][j]!='Z')//如果是管道
				{
					if(!book[i][j])//如果没走过
						flag2=false;
				}
			}
		}
		if(flag2)
		{
			if(hack) --block;
		    cout<<fixx<<" "<<fixy<<" "<<bl[block];//满足所有的要求就是答案了，可以直接退出
		    exit(0);
		}
	}
	else if(flag)//第一次进入
	{
		flag=false;
		fixx=x+nt[p-1][0],fixy=y+nt[p-1][1];
	}
}

int main()
{
	cin>>r>>c;
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<=c;j++)
		{
			cin>>e[i][j];
			if(e[i][j]=='M')
			{
				sx=i;
				sy=j;
			}
			if(e[i][j]=='Z')
			{
				fx=i;
				fy=j;
			}
		}
	}
    
    //定义哪些可以走
	
	_left['+']=1;
	_left['-']=1;
	_left['1']=1;
	_left['2']=1;
	
	up['+']=1;
	up['|']=1;
	up['1']=1;
	up['4']=1;
	
	_right['+']=1;
	_right['-']=1;
	_right['3']=1;
	_right['4']=1;
	
	down['+']=1;
	down['|']=1;
	down['2']=1;
	down['3']=1;
	
	check();
	f(sx+nt[dir-1][0],sy+nt[dir-1][1],dir);//第一遍调用找到缺少的坐标
	
	if(fixx == sx && fixy == sy){ //新增的Hack内容 
		hack = true;
		for(; block >= 0; block--){
			for(int i=0; i<4; i++){
				int x = sx + nt[i][0];
				int y = sy + nt[i][1];
				if(e[x][y] == '.'){
					e[x][y] = bl[max(0, block)];
					fixx = x, fixy = y;
					check();
					f(sx+nt[dir-1][0],sy+nt[dir-1][1],dir);
					e[x][y] = '.';
				}
			}
		}
	}
	
	while(block>=0)
	{
		memset(book, 0, sizeof(book));//每次枚举要重置book数组
		
		if(!flag)e[fixx][fixy]=bl[max(0,block)];//将枚举的管道拼接到地图中
		
		f(sx+nt[dir-1][0],sy+nt[dir-1][1],dir);
		block--;//记得从后向前枚举，前文有提及
	}
}

实测满分。

本蒟蒻的第六篇题解。