自动搬运

查看原文

来自洛谷，原作者为

	Ice_Kissღ 我已经无路可退

搬运于2025-08-24 21:27:55，当前版本为作者最后更新于2020-11-14 11:39:10，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

添加了一些说明呢 $qwq$

哎呀，从今年提高组游过后，我深感模拟的重要性！

于是便写了这道大模拟，借此来练一下手感。

好了，话不多说，我们进入正题：

首先看到这题后，我们会发现，题目要我们求最小的路径长度与其对应的 开始点与结束点。

实际只要求出最小路径其他均可迎刃而解。

再看看题目，你会发现一句关键的话：捷径必须是直线。

这意味着小蓉蓉只可找一条笔直的最短路径，而且它的出发点与结束点必定是含有相同横坐标或相同纵坐标的！

而我们怎么找到相同横坐标或相同纵坐标呢，不难想到，只用对横纵坐标分别进行排序即可。

而另外一个关于出发点与结束点的问题我们可以通过点编号的大小（也就是小蓉蓉到达的先后）来判断。

特别提醒： 如果检索到的两个点编号差为一（它们相邻），则必要舍弃这题最短路经。你问为什么？因为它们之间已经有路了啊！

那本题即可变为：

• 在一张给定的图中找到最短的有横坐标或纵坐标相同的两个点的距离，有多组情况时，选起始点最小的；若还存在多组情况，选结束点最大的。

分析结束~

那之后就是轻松的手动模拟了（速度飞快）。

还有一些关键点在代码中提到。

#include<bits/stdc++.h>
using namespace std;
int n; 
string s;
int minn=1e9;
int here=1e9,to=-1e9;
char xiang;
struct node
{
	int x;int y;
	int bian;
}rong[250005];
bool cmp1(node a,node b)
{
	return a.x<b.x || (a.x==b.x && a.y<b.y);
}
bool cmp2(node a,node b)
{
	return a.y<b.y || (a.y==b.y && a.x<b.x);
}
//两个排序，不用多说。
void jx()
{
	int tmp,a,b;
	char er;
	for(int i=1;i<=n-1;i++)
	{
		if(rong[i].x==rong[i+1].x)//找到相同横坐标时
		{
			tmp=abs(rong[i].y-rong[i+1].y);//记录路径长度
			if(rong[i].bian<rong[i+1].bian)//根据编号大小判断出发点与终点
		    {
			    a=rong[i].bian;
			    b=rong[i+1].bian;		
				if(rong[i].y<rong[i+1].y) er='N';//别忘了方向记录
				else er='S';
                
		    }
		    else //同理
		    {
			    a=rong[i+1].bian;
			    b=rong[i].bian;		
				if(rong[i+1].y<rong[i].y) er='N';
				else er='S';
		    }
			if(a+1==b) continue;//如果编号相邻则已有路径，舍去
			if(minn==tmp)//进行最终决策
			{
				if(here>a) 
				{
					minn=tmp; here=a; to=b; xiang=er;
				}
				else if(here==a)
				{
					if(b>to)
				    {
				    	minn=tmp; here=a; to=b; xiang=er;
					}
				}
			}
			if(minn>tmp)
			{
				minn=tmp; here=a; to=b; xiang=er;
			}
            
	    }	
	}
}
void jy()
{
	int tmp,a,b;
	char er;
	for(int i=1;i<=n-1;i++)
	{
		if(rong[i].y==rong[i+1].y)//找到相同纵坐标时
		{
			tmp=abs(rong[i].x-rong[i+1].x);//记录路径长度
			if(rong[i].bian<rong[i+1].bian)//根据编号大小判断出发点与终点
		    {
			    a=rong[i].bian;
			    b=rong[i+1].bian;		
				if(rong[i].x<rong[i+1].x) er='E';//别忘了方向记录
				else er='W';
		    }
		    else //同理
		    {
			    a=rong[i+1].bian;
			    b=rong[i].bian;		
				if(rong[i+1].x<rong[i].x) er='E';
				else er='W';
		    }
			if(a+1==b) continue;//如果编号相邻则已有路径，舍去
			if(minn==tmp)//进行最终决策
			{
				if(here>a) 
				{
					minn=tmp; here=a; to=b; xiang=er;
				}
				else if(here==a)
				{
					if(b>to)
				    {
				    	minn=tmp; here=a; to=b; xiang=er;
					}
				}
			}
			if(minn>tmp)
			{
				minn=tmp; here=a; to=b; xiang=er;
			}
	    }	
	}
}
int main()
{
	scanf("%d",&n);
	cin>>s;
	rong[0].x=250005;rong[0].y=250005;//防止出现负数。
	for(int i=0;i<n;i++)
	{
		int k=i+1;
		rong[k].bian=k;
		rong[k].x=rong[k-1].x;
		rong[k].y=rong[k-1].y;
		if(s[i]=='N') rong[k].y++;
	    if(s[i]=='W') rong[k].x--;
	    if(s[i]=='E') rong[k].x++;
	    if(s[i]=='S') rong[k].y--;
	}
	sort(rong+1,rong+1+n,cmp1);//横坐标排序。
	jx();//查找。
	sort(rong+1,rong+1+n,cmp2);//纵坐标排序。
	jy();//查找。
	cout<<minn<<" "<<here<<" "<<to<<" "<<xiang;
	return 0;
}

完结撒花 $QAQ$

求赞赞！