此题用的广搜加记忆化，一开始没考虑方向，测试数据都过不了，在队友的提醒下才发现，改了之后广搜过了，深搜却错了，调了无数个小错误之后，终于过了测试数据，汗啊！！！交上去却Wrong了，但是就郁闷啦，逻辑明明没错了，最后还是在队友的帮助下才发现没考虑终点不可达的情况。功夫不负有心人，断断续续等了一个星期，终于AC了。

 

ACcode：

 

#include<stdio.h>
#include<queue>
#include<iostream>
using namespace std;
const int size=1010;
const int MAX=1000000001;
struct Point 
{
int x,y,step,dir;
}end,start;
void bfs();
int dfs(Point cur);
bool ismap(Point a);
int judgestr(char c);
void insert(Point next);
int stepnum(Point next,Point cur);
int n,m,mo;
queue<Point> q; 
char str[size][size],c;
int num[size][size][4],dp[size][size][4];
Point dir[4]={{1,0},{0,-1},{-1,0},{0,1}};
int judgestr(char c)
{
if (c=='N') return 0;
else if (c=='E') return 1;
else if (c=='S') return 2;
else return 3;
}
bool ismap(Point a)
{
if (a.x<0||a.x>=n||a.y<0||a.y>=m||str[a.x][a.y]=='*') return false;
return true;
}
void insert(Point next)
{
if (ismap(next)&&next.step<num[next.x][next.y][next.dir])
{
num[next.x][next.y][next.dir]=next.step;
q.push(next);
}
return ;
}
void bfs()
{
int i,j,k;
Point t,next;
t.x=end.x,t.y=end.y,t.step=0;
while (!q.empty()) q.pop();
for (i=0;i<4;i++) 
{
t.dir=i;
q.push(t);    
}    
while (!q.empty())
{
t=q.front();
q.pop();  
next.x=t.x+dir[t.dir].x;
next.y=t.y+dir[t.dir].y;
next.dir=t.dir;
if (next.step!=MAX)
{
next.step=t.step+1;
insert(next);
}
next.x=t.x;
next.y=t.y;
next.dir=(t.dir+1)%4;
if (next.step!=MAX)
{
next.step=t.step+1;
insert(next);
}
next.dir=(t.dir+3)%4;
if (next.step!=MAX)
{
next.step=t.step+1;
insert(next);
}
}
return ;
}
int stepnum(Point next,Point cur)
{
if (ismap(next)&&num[next.x][next.y][next.dir]==num[cur.x][cur.y][cur.dir]-1)
return dfs(next);  
else return 0;
}
int dfs(Point cur)
{
if (dp[cur.x][cur.y][cur.dir]) return dp[cur.x][cur.y][cur.dir]; 
int i,ans=0;
Point next;
next.x=cur.x+dir[(cur.dir+2)%4].x;
next.y=cur.y+dir[(cur.dir+2)%4].y;
next.dir=cur.dir;
ans=(ans+stepnum(next,cur))%mo;
next.x=cur.x;
next.y=cur.y;
next.dir=(cur.dir+1)%4;
ans=(ans+stepnum(next,cur))%mo;
next.dir=(cur.dir+3)%4;
ans=(ans+stepnum(next,cur))%mo;
dp[cur.x][cur.y][cur.dir]=ans;
return ans;
}
int main()
{
int i,j,k,cas=0;
while (scanf("%d %d %d",&n,&m,&mo)&&n&&m&&mo)
{
for (i=0;i<n;i++) scanf("%s",str[i]);
scanf("%d %d %d %d %c",&start.x,&start.y,&end.x,&end.y,&c);
start.dir=judgestr(c);
for (i=0;i<n;i++) for (j=0;j<m;j++) 
for (k=0;k<4;k++) num[i][j][k]=MAX,dp[i][j][k]=0;
for (i=0,k=-1;i<4;i++) num[end.x][end.y][i]=0,dp[end.x][end.y][i]=1;
bfs();
if (num[start.x][start.y][start.dir]!=MAX&&str[end.x][end.y]!='*') k=dfs(start);
printf("Case %d: %d %d\n",++cas,mo,k);   
}
return 0;   
}