麻烦的处理，然后写写写，码农题
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<queue>
#include<string>
#include<vector>
#include<set>
#include<algorithm>
#define maxn 1<<29
using namespace std;
char a[555][555];
bool c[555][555][4];
bool z[555][555][4];
int xx[4]= {-1,0,1,0};
int yy[4]= {0,-1,0,1};
int n,t;
int sx,sy,tx,ty;
int r[555][555];
bool vis[555][555];
void solve()
{
memset(vis,0,sizeof(vis));
queue<int>q;
q.push(sx*n+sy);
vis[sx][sy]=1;
r[sx][sy]=0;
while(!q.empty())
{
int u=q.front();
q.pop();
int ux=u/n;
int uy=u%n;
vis[ux][uy]=0;
for(int i=0; i<4; i++)
{
int vx=ux+xx[i];
int vy=uy+yy[i];
if(vx>=n||vx<0||vy>=n||vy<0)continue;
if(a[vx][vy]=='#')continue;
for(int j=0; j<4; j++)
{
int tt=r[ux][uy]+j+1;
if(z[ux][uy][(tt+3)%4]==0&&c[vx][vy][tt%4]==0)
{
if(tt<r[vx][vy])
{
r[vx][vy]=tt;
if(!vis[vx][vy])
{
vis[vx][vy]=1;
q.push(vx*n+vy);
}
}
}
}
if(r[vx][vy]>r[ux][uy]+3)
{
r[vx][vy]=r[ux][uy]+3;
if(!vis[vx][vy])
{
vis[vx][vy]=1;
q.push(vx*n+vy);
}
}
//cout<<vx<<" "<<vy<<" "<<r[vx][vy]<<endl;
}
}
}
int main()
{
int ca=1;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=0; i<n; i++)scanf("%s",a[i]);
memset(c,0,sizeof(c));
memset(z,0,sizeof(z));
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
r[i][j]=maxn;
if(a[i][j]=='M')
{
sx=i;
sy=j;
}
else if(a[i][j]=='T')
{
tx=i;
ty=j;
}
else if(a[i][j]=='N')
{
for(int kk=0; kk<4; kk++)
{
z[i][j][kk]=1;
c[i][j][kk]=1;
}
if(i-1>=0)
{
z[i-1][j][0]=1;
//c[i-1][j][0]=1;
c[i-1][j][1]=1;
}
if(j-1>=0)
{
z[i][j-1][3]=1;
//c[i][j-1][3]=1;
c[i][j-1][0]=1;
}
if(i+1<n)
{
z[i+1][j][2]=1;
//c[i+1][j][2]=1;
c[i+1][j][3]=1;
}
if(j+1<n)
{
z[i][j+1][1]=1;
//c[i][j+1][3]=1;
c[i][j+1][2]=1;
}
}
else if(a[i][j]=='W')
{
for(int kk=0; kk<4; kk++)
{
z[i][j][kk]=1;
c[i][j][kk]=1;
}
if(i-1>=0)
{
z[i-1][j][1]=1;
//c[i-1][j][3]=1;
c[i-1][j][2]=1;
}
if(j-1>=0)
{
z[i][j-1][0]=1;
//c[i][j-1][0]=1;
c[i][j-1][1]=1;
}
if(i+1<n)
{
z[i+1][j][3]=1;
//c[i+1][j][1]=1;
c[i+1][j][0]=1;
}
if(j+1<n)
{
z[i][j+1][2]=1;
//c[i][j+1][2]=1;
c[i][j+1][3]=1;
}
}
else if(a[i][j]=='S')
{
for(int kk=0; kk<4; kk++)
{
z[i][j][kk]=1;
c[i][j][kk]=1;
}
if(i-1>=0)
{
z[i-1][j][2]=1;
//c[i-1][j][2]=1;
c[i-1][j][3]=1;
}
if(j-1>=0)
{
z[i][j-1][1]=1;
//c[i][j-1][3]=1;
c[i][j-1][2]=1;
}
if(i+1<n)
{
z[i+1][j][0]=1;
//c[i+1][j][0]=1;
c[i+1][j][1]=1;
}
if(j+1<n)
{
z[i][j+1][3]=1;
//c[i][j+1][1]=1;
c[i][j+1][0]=1;
}
}
else if(a[i][j]=='E')
{
for(int kk=0; kk<4; kk++)
{
z[i][j][kk]=1;
c[i][j][kk]=1;
}
if(i-1>=0)
{
z[i-1][j][3]=1;
//c[i-1][j][1]=1;
c[i-1][j][0]=1;
}
if(j-1>=0)
{
z[i][j-1][2]=1;
//c[i][j-1][2]=1;
c[i][j-1][3]=1;
}
if(i+1<n)
{
z[i+1][j][1]=1;
//c[i+1][j][3]=1;
c[i+1][j][2]=1;
}
if(j+1<n)
{
z[i][j+1][0]=1;
//c[i][j+1][0]=1;
c[i][j+1][1]=1;
}
}
}
}
solve();
printf("Case #%d: ",ca++);
if(r[tx][ty]==maxn)printf("-1\n");
else printf("%d\n",r[tx][ty]);
}
return 0;
}
/*
5
3
MN.
NN.
..T
3
MNN
NNN
T..
*/