自动搬运

查看原文

来自洛谷，原作者为

	world_execute I swear I'll follow through.

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

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

以下是正文

[ 更好的阅读体验 ]

[ 原题面 ]

第零部分 —— 阅读题目

• 题目大意：幽暗城中有三个人，萨尔 Sal ，恐惧魔王 Dread Lord ，And 小A。刚开始，小A与萨尔在 $(x1,y1)$ 位置，而恐惧魔王在 $(x2,y2)$ 位置。小A想要走到恐惧魔王的位置，但不能离萨尔d个单位距离以上超过s秒，同时，萨尔与恐惧魔王都会按照各自的模式，固定的行走。

• 输入：幽暗城的地图，0表示可以走，1表示被挡住，不能走。

• 数据范围：1 $\le$ 地图长、宽 $ \le $50，0$ \le $最大离开时间$ \le $1000，0$ \le $最大离开距离$ \le $ 100，计算欧几里得距离（直线距离）

• So， $O(nm * 答案大小 * 一个非常大的常数)$的算法似乎轻松可以过，而且跑的飞快。

第一部分 —— 开始分析

• 似乎可以用搜索做，但是有好多问题有待解决，如离开时间、每个时间上，萨尔与恐惧魔王的位置，搜索陷入死循环，被困在圈内……

• 可是有什么困难可以阻挡我们AC这道题的脚步呢？我们把这些难点逐个突破，一定可以做出的。

• So，我们初步确定了算法，可以开始着手思考一些细节了。

第三部分 —— 深入思考

• So Good，我们先解决陷入一个死循环。

• 有人会说，为何会进入死循环？那时的情况Looks like this:

             ...1111...
             ...1001...
             ...1000<-.
             ...1001...
             ...1111...
   (从箭头所指处进入，先判断上，所以无法退出）
  

• And，how to do？我们可以百度搜索：迭代加深搜索。（用力划掉(* /ω＼ *)）

• 迭代加深搜索（IDDFS）可以有效地避免搜索层数过多，导致的TLE。

• 具体来说迭代加深搜索就是在每次搜索时，限定一个最大搜索层数，每当超过Max_Deep时return，具体实现将会在 第五部分——代码实现 部分具体讲述，不用急，在你看过下面的解析后，可以根据它的定义，不看代码就写出来。

• 所有新知识都讲完了呢ヽ(✿ﾟ▽ﾟ)ノ。（巨佬请无视此句）

• Haha，萨尔的位置与恐惧魔王的位置怎么办呢？预处理呀，利用生成串来预处理，因为他们 （你怎么知道是“他们”而不是“她们”或“它们”的呢） 的位置只与时间有关，和小A的位置无关

• 还有，对于离开的时间如何进行判断？按题意判断就好了呀。（QAQ）

• So，是不是可以开始码代码了呢？我相信你有这个实力，去吧，（关了题解去码吧） 去看下一部分，那里较为详细地讲述了如何代码实现此题。

第五部分 —— 代码实现

• 输入部分：讲一下吧，本人认为这部分有些难度，机房几位巨佬都一不小心写错了呢。

scanf("%d%d%d%d", &n, &m, &s, &r);	//输入地图大小，最长离开时间，最大光环距离
for (int i=1; i<=n; ++i)
	for (int j=1; j<=m; ++j)
		cin>>ch,Map[i][j]=(ch-48);	//输入地图
scanf("%d%d%d%d", &Salx[0], &Saly[0], &Lorx[0], &Lory[0]);	//输入x1,y1,x2,y2
cin>>st_Sal;	//输入萨尔的位置生成串
cin>>st_Lor;	//输入恐惧魔王的的位置生成串

• Sal 即 萨尔的英文， Lor 即 Dread Lord的缩写 也就是 恐惧魔王的英文。（举报，有人机房打“Saly” o(￣▽￣)ｄ）

• 然后就是对答案等于0时的预处理

         (Salx[0]==Lorx[0] && Saly[0]==Lory[0])
  

• 再是对萨尔位置与魔王位置的Preprocessing。

• 这段代码本人写的十分丑陋，但还是放上来吧：

for (int i=1; i<=100; ++i)	//生成100次之内的位置
{
	int tx = Lorx[i-1]+bak[st_Lor[(i-1)%st_Lor.length()]-48];	//Bak即位置预处理数组
	int ty = Lory[i-1]+bak[st_Lor[(i-1)%st_Lor.length()]-43];	//此时减去43是因为在减48的同时要加5，因为这是对y坐标的更改，不能和x坐标混淆
	if ((tx<1)||(tx>n)||(ty<1)||(ty>m))	//走出边界
		tx = Lorx[i-1],ty = Lory[i-1];
	else if (Map[tx][ty] == 1)	//撞上墙
		tx = Lorx[i-1],ty = Lory[i-1];
	Lorx[i] = tx,Lory[i] = ty;

	tx = Salx[i-1]+bak[st_Sal[(i-1)%st_Sal.length()]-48];
	ty = Saly[i-1]+bak[st_Sal[(i-1)%st_Sal.length()]-43];
	if ((tx<1)||(tx>n)||(ty<1)||(ty>m))
		tx = Salx[i-1],ty = Saly[i-1];
	else if (Map[tx][ty] == 1)
		tx = Salx[i-1],ty = Saly[i-1];
	Salx[i] = tx,Saly[i] = ty;
}

• 下面生成Sal的位置与Lor位置是一样的，就不写注释了。

• 然后主程序的最后一段：枚举Max_Deep，然后带入搜索：

for (int i=1; i<=100; ++i)
	Search(i,0,Salx[0],Saly[0],0);	//i表示最大深度，第一个0表示现在小A走的步数，Salx[0]表示开始时的x坐标，Saly表示开始时的y坐标，最后一个0表示已经离开0秒

• 最后就是Search部分

void Search(int Max_Deep,int now,int nx,int ny,int Leave_Time)
{
	if (现在层数大于最大层数 或 离开时间大于s)
		return;
	if (到达魔王的位置)
	{
		printf("%d\n", now);
		exit(0);
	}
	now ++;	//开始走
	for (int i=0; i<5; ++i)//五种方案：上下左右或者不动
	{
		int tx = nx+bak[i];
		int ty = ny+bak[i+5];
		int tk = Leave_Time;
		if ((tx<1)||(tx>n)||(ty<1)||(ty>m))
			continue;
		if (Map[tx][ty] == 1)
			continue;
		if (dist(tx,ty,Salx[now],Saly[now]) > r)
			tk++;
		else tk = 0;
		Search(Max_Deep,now,tx,ty,tk);
	}
}

• So，第五部分的代码实现就解决了，是不是觉得还比较简单，还有本人第二次在洛谷发布题解，不知道如何写才好，如果有没讲清楚的地方，尽管在评论中回复，我尽量做到有问必答。

第六部分 —— 后记

• 不知不觉就写了这么多了呢，希望各位给我一个赞，或是给予我您的宝贵的意见

• So，题解就到这了吧