非常水的一道题。

对于两个相邻格子，如果可以直接到达，连一条边权为 $0$ 的边；如果转一次就可以直接到达，连一条边权为 $1$ 的边；以此类推。

剩下的就是 SPFA 了，它没死。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
int n,m,a[510][510],d[510][510];
int dx[]={0,-1,0,1,0};
int dy[]={0,0,1,0,-1};
struct node{int x,y;};
void spfa()
{
    memset(d,999999,sizeof(d));
    if(!a[1][1]&&(n!=1||m!=1))return;
    d[1][1]=0;
    queue<node>q;
    q.push({1,1});
    while(!q.empty())
    {
        int x=q.front().x,y=q.front().y;
        q.pop();
        for(int i=1;i<=4;i++)
        {
            int nx=x+dx[i],ny=y+dy[i];
            if(nx<1||nx>n||ny<1||ny>m)continue;
            if(!a[nx][ny]&&(nx!=n||ny!=m))continue;
            int w=(i+4-a[x][y])%4;
            if(d[x][y]+w<d[nx][ny])
            {
                d[nx][ny]=d[x][y]+w;
                q.push({nx,ny});
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            char c;
            cin>>c;
            if(c=='N')a[i][j]=1;
            if(c=='E')a[i][j]=2;
            if(c=='S')a[i][j]=3;
            if(c=='W')a[i][j]=4;
        }
    spfa();
    if(d[n][m]<1e9)cout<<d[n][m]<<endl;
    else cout<<-1<<endl;
    return 0;
}

与此题非常类似的另一道题是 P4667，请自行练习。