题意：

给你一幅图，给你起点和终点，再给你机器人所面对的方向，机器人可以左转90°，右转90°，向前进一格，每种操作都是1秒，,求起点和终点最少花费下的路径条数，方案数；

思路：

这里有一个不同就是机器人还有一个先转弯，再前进。

一开始想的是最短路，问题就是最短路计数，后来一直WA；

后来原来是写挫了，想的是最短路计数，然后写的是BFS，而且连图都没有建，直接跑spfa，也不知道在干什么。

好像最短路的话建图似乎很麻烦，而且复杂度和可行度比这个简单BFS一下低很多；

基础BFS，在一个位置，他可以左转，右转，前进，那么每次枚举状态，通过步数进行标记。

如果一个状态的步数>前一状态所到达他的步数，那么方案数=之前的方案数；

如果相等，那么就累加。

#include <bits/stdc++.h>
using namespace std;
const int INF=0x7f7f7f7f;
const int N=1e3+10;
char s[N][N];
int sx,sy,ex,ey;struct asd{int x,y;int flag;
};int dx[4]={1,-1,0,0}; // S N E W
int dy[4]={0,0,1,-1};
int mod;
int n,m;
bool vis[N][N][4];
int num[N][N][4];
int ans[N][N][4];int check(char x)
{if(x=='S') return 0;if(x=='N') return 1;if(x=='E') return 2;if(x=='W') return 3;
}
queue<asd>q;void init()
{while(!q.empty())q.pop();memset(vis,0,sizeof(vis));memset(num,-1,sizeof(num));memset(ans,0,sizeof(ans));
}bool Judge(int xx,int yy)
{if(xx<0||yy<0||xx>=n||yy>=m||s[xx][yy]=='*')return 0;return 1;
}
bool diff_dir(int x,int y)
{if((x==0||x==1)&&(y==2||y==3))return 1;swap(x,y);if((x==0||x==1)&&(y==2||y==3))return 1;return 0;
}void bfs(char x)
{init();asd sta;sta.flag=check(x);sta.x=sx;sta.y=sy;vis[sta.x][sta.y][sta.flag]=1;ans[sta.x][sta.y][sta.flag]=1;num[sta.x][sta.y][sta.flag]=0;q.push(sta);asd now,next;while(!q.empty()){now=q.front();q.pop();for(int i=0;i<4;i++){if(diff_dir(i,now.flag)){if(num[now.x][now.y][i]==-1){num[now.x][now.y][i]=num[now.x][now.y][now.flag]+1;ans[now.x][now.y][i]=ans[now.x][now.y][now.flag];next=now;next.flag=i;q.push(next);}else if(num[now.x][now.y][i]==num[now.x][now.y][now.flag]+1)ans[now.x][now.y][i]=(ans[now.x][now.y][i]+ans[now.x][now.y][now.flag])%mod;}}next.x=now.x+dx[now.flag];next.y=now.y+dy[now.flag];next.flag=now.flag;if(Judge(next.x,next.y)){if(num[next.x][next.y][now.flag]==-1){num[next.x][next.y][next.flag]=num[now.x][now.y][now.flag]+1;ans[next.x][next.y][next.flag]=ans[now.x][now.y][now.flag];q.push(next);}else if(num[next.x][next.y][next.flag]==num[now.x][now.y][now.flag]+1)ans[next.x][next.y][next.flag]=(ans[next.x][next.y][next.flag]+ans[now.x][now.y][now.flag])%mod;}}int temp=INF;int res=0;for(int i=0;i<4;i++){if(num[ex][ey][i]!=-1){if(temp>num[ex][ey][i])temp=num[ex][ey][i];}}if(temp==INF){puts("-1");return;}for(int i=0;i<4;i++){if(temp==num[ex][ey][i])res=(res+ans[ex][ey][i])%mod;}printf("%d\n",res);
}
int main()
{int cas=1;while(~scanf("%d%d%d",&n,&m,&mod)){if(!mod)break;for(int i=0;i<n;i++)scanf("%s",s[i]);char x;scanf("%d %d %d %d %c",&sx,&sy,&ex,&ey,&x);printf("Case %d: %d ",cas++,mod);bfs(x);}return 0;
}