自动搬运

查看原文

来自洛谷，原作者为

	Lice 这个人懒散惯了，什么都没写

搬运于2025-08-24 22:18:49，当前版本为作者最后更新于2020-03-22 13:56:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Description

它 spfa 了

Solution

显然直接胡乱转是行不通的。

然而正解是图论中的最短路。

那样例1来说：

EES
SSW
ESX

假如你现在要从 $(0,1)$ 走到 $(1,1)$，的话，如果不绕圈子，那么我们需要将位置 $(0,1)$ 的箭头旋转一次，然后就可以走过去了。这可以抽象成： 从顶点 $(0,1)$ 有一条到 $(1,1)$ 的边，边权为1。其他的位置同理，以位置之间移动的所需旋转次数为边权 。如果是 X 的话，就把它的所有出边边权设成 inf 。

那么对这个箭头矩阵进行这样的转化之后，我们得到了一张这样的图：

然后？直接跑最短路就好啦！

下面用了 Dijkstra 算法，spfa 应该可以（这个坑留个下一个题解）。

Code

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

const int dx[4]={0,0,-1,1};
const int dy[4]={-1,1,0,0};
const char dir[]="WENS";

int val[256];
const int N=502;
char s[N][N];
int dist[N][N];
bool book[N][N];
int n,m;

int cost(char a,char b)//计算字符（箭头）转化的花费
{
	int sub=val[(int)b]-val[(int)a];
	if(sub<0) sub+=4;
	return sub;
}

struct HeapNode
{
	int x,y,dis;
	HeapNode(int _x,int _y,int _d):x(_x),y(_y),dis(_d){}
	bool operator <(const HeapNode &t)const{return dis>t.dis;}
};

bool out_of_range(int x,int y)
{
	return (x<1||y<1||x>n||y>m);
}

void SSSP()//建不建图其实无所谓，可以直接在原矩阵上跑。但是建图的话就可以直接套板子了，少了一些判断。
{//堆优化 Dijkstra 板子
	priority_queue<HeapNode> Q;
	Q.push(HeapNode(1,1,dist[1][1]=0));
	while(!Q.empty())
	{
		int x=Q.top().x,y=Q.top().y;
		Q.pop();
		if(book[x][y]) continue;
		book[x][y]=true;
		if(s[x][y]=='X') continue;
		for(register int i=0;i<4;i++)
		{
			HeapNode nxt(x+dx[i],y+dy[i],dist[x][y]+cost(s[x][y],dir[i]));
			if(out_of_range(nxt.x,nxt.y)) continue;
			if(dist[nxt.x][nxt.y]<=nxt.dis) continue;
			dist[nxt.x][nxt.y]=nxt.dis;
			Q.push(HeapNode(nxt));
		}
	}
}

signed main()
{
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=n;i++)
		scanf("%s",s[i]+1);
	
	memset(dist,0x3f,sizeof dist);
	memset(book,false,sizeof book);
	val['W']=0,val['N']=1;
	val['E']=2,val['S']=3;
	
	SSSP();
	printf("%d\n",dist[n][m]==0x3f3f3f3f?-1:dist[n][m]);
	return 0;
}

应该是第一篇题解，如果帮到了你不妨点个赞啊 awa