🧩题解思路

建图：将地图转为逻辑上的网格图，每个交叉点是一个节点，使用宽度优先搜索（BFS）；

记录路径：在 BFS 中记录父节点，用于回溯最短路径；

方向合并：最终回溯出路径后，对连续相同方向的移动进行合并；

输出格式：按照“方向 + 步数”格式输出。

🧠小贴士

地图解析比较特殊，可以将每个 '+' 节点作为 $(x,y)$ 坐标系中的节点；

BFS 是求最短路径的利器；

合并方向是最后的后处理步骤；

注意输入地图格式是行列交错的，行索引为奇偶有不同含义。

代码实现

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 1001
#define MOD 123
#define E 1e-6
using namespace std;
int n,e;
char g[N][N];
char path[N*N];
int vis[N][N];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
struct Node{
	int x;
	int y;
}pre[N][N];
queue<Node> q;
char get_dir(int x,int y,int turn_x,int turn_y)//获取转向方向
{
	for(int i=0;i<4;i++)
	{
		int nx=x+dir[i][0];
		int ny=y+dir[i][1];
		
		if(nx==turn_x&&ny==turn_y)
		{
			if(i==0)
				return 'E';
			else if(i==1)
				return 'W';
			else if(i==2)
				return 'S';
			else
				return 'N';
		}
	}
	return 0;
}
void bfs(int x,int y)
{
	q.push({y,x});//压入始点
	pre[x][y].x=-1;
	pre[x][y].y=-1;
	vis[x][y]=1;
	
	while(!q.empty())
	{
		Node pos=q.front();
		q.pop();
		
		if(g[pos.y][pos.x]=='E')
			break;
		
		for(int i=0;i<4;i++)
		{
			int nx=pos.x+dir[i][0];
			int ny=pos.y+dir[i][1];
			
			if(nx<0||nx>=e||ny<0||ny>=n||vis[ny][nx]||g[ny][nx]=='.')//越界判断
				continue;
			
			pre[ny][nx]=pos;
			vis[ny][nx]=1;
			q.push({nx,ny});//将路径压入队列
		}
	}
}
void print(int x,int y)
{
	int cnt=0;
	Node pos=pre[x][y],last;
	
	last.x=y;
	last.y=x;
	
	while(pos.x!=-1&&pos.y!=-1)
	{
		path[cnt++]=get_dir(pos.x,pos.y,last.x,last.y);//获取行进方向
		while(g[pos.y][pos.x]=='-' || g[pos.y][pos.x]=='|')
		{
			last=pos;
			pos=pre[last.y][last.x];
		}
		
		last=pos;
		pos=pre[last.y][last.x];
	}
	
	for(int i=cnt-1;i>=0;i--)
	{
		int sum=0;
		char last_dir=path[i];
		while(i>=0&&last_dir==path[i])//如果转向方向与路径方向相同
		{
			i--;
			sum++;
		}
		
		printf("%c %d\n",last_dir,sum);
		
		if(last_dir!=path[i])//如果转向方向与路径方向不同
			i++;
	}
	
}
int main()
{
	scanf("%d%d",&n,&e);
	
	n=n*2-1;//图的真实横长
	e=e*2-1;//图的真实纵长
	
	for(int i=0;i<n;i++)
		scanf("%s",g[i]);
	
	int start_x,start_y,end_x,end_y;
	for(int i=0;i<n;i++)//记录始点与终点
	{
		for(int j=0;j<e;j++)
		{
			if(g[i][j]=='S')
			{
				start_x=i;
				start_y=j;
			}
			if(g[i][j]=='E')
			{
				end_x=i;
				end_y=j;
			}
		}
	}
	
	bfs(start_x,start_y);//bfs搜索
	
	print(end_x,end_y);//输出
	
	return 0;
}