/*
剪枝：四秒后状态会变得和原来一样，所以四秒后如果再经过这个点肯定不是最优的舍去
易错点：在一个是从.到.这两个点都没有被照到并且不是摄像机，也可能需要等3秒，因为后面的结果可能再这三秒中发生改变，要单独判断
*/
#include<stdio.h>
#include<queue>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 510
char s[N][N];
struct node {
int x,y,time;
  friend bool operator<(node a,node b) {//优先队列
   return a.time>b.time;//从小到大出队
  }
}ss,tt,next,cu;
int ma[N][N][4],n;
int judge(int x,int y) {
  if(x>=1&&x<=n&&y>=1&&y<=n)
     return 1;
  return 0;
}
void update(int i,int j,char ch) {//存关于时间的状态
  if(ch=='N') {
    if(judge(i-1,j))ma[i-1][j][0]=1;
    if(judge(i,j+1))ma[i][j+1][1]=1;
     if(judge(i+1,j))ma[i+1][j][2]=1;
     if(judge(i,j-1))ma[i][j-1][3]=1;
  }
    if(ch=='W') {
    if(judge(i,j-1))ma[i][j-1][0]=1;
    if(judge(i-1,j))ma[i-1][j][1]=1;
     if(judge(i,j+1))ma[i][j+1][2]=1;
     if(judge(i+1,j))ma[i+1][j][3]=1;
  }
    if(ch=='S') {
    if(judge(i+1,j))ma[i+1][j][0]=1;
    if(judge(i,j-1))ma[i][j-1][1]=1;
     if(judge(i-1,j))ma[i-1][j][2]=1;
     if(judge(i,j+1))ma[i][j+1][3]=1;
  }
    if(ch=='E') {
    if(judge(i,j+1))ma[i][j+1][0]=1;
    if(judge(i+1,j))ma[i+1][j][1]=1;
     if(judge(i,j-1))ma[i][j-1][2]=1;
     if(judge(i-1,j))ma[i-1][j][3]=1;
  }
}
int dis[4][2]={1,0,-1,0,0,1,0,-1},vis[N][N][5];
int bfs() {
  int i,xx,yy;
  priority_queue<node>q;
  memset(vis,0,sizeof(vis));
  ss.time=0;
  q.push(ss);
  while(!q.empty()) {
    ss=q.top();
    q.pop();
    if(ss.x==tt.x&&ss.y==tt.y)return ss.time;
    //if(ss.time>=800000)break
     cu=ss;cu.time++;//考虑不够完善，刚开始写的时候写到了for循环里面，这是不对的，因为。到。 等不超过四秒可能会有不同结果。
    if(vis[cu.x][cu.y][cu.time%4]==0) {//等待，最多不超过三秒
            vis[cu.x][cu.y][cu.time%4]=1;
            q.push(cu);
    };
    for(i=0;i<4;i++) {
        next.x=xx=ss.x+dis[i][0];
        next.y=yy=ss.y+dis[i][1];
        if(judge(xx,yy)&&s[xx][yy]!='#') {
              //  printf("%d %d\n",xx,yy);
            if(s[ss.x][ss.y]!='.'||ma[ss.x][ss.y][ss.time%4]||ma[xx][yy][ss.time%4]||s[xx][yy]!='.') {//如果当前点或者下一个点被照到，或者当前点和下一个点都是摄像机，那么移动的话需要时间+3
                next.time=ss.time+3;
                if(vis[next.x][next.y][next.time%4]==0) {
                vis[next.x][next.y][next.time%4]=1;
                q.push(next);
                }
                 continue;
            }
                next.time=ss.time+1;
                if(vis[xx][yy][next.time%4]==0) {//如果是.到.的话也可以不等待
                vis[xx][yy][next.time%4]=1;
                q.push(next);
                }
        }
    }
  }
  return -1;
}
int main() {
     int  i,j,t,f=0;
     scanf("%d",&t);
     while(t--) {
        scanf("%d",&n);
        for(i=1;i<=n;i++)
            scanf("%s",s[i]+1);
         memset(ma,0,sizeof(ma));
         for(i=1;i<=n;i++)
         for(j=1;j<=n;j++) {
            if(s[i][j]=='M') {
                s[i][j]='.';
                ss.x=i;
                ss.y=j;
            }
            else
            if(s[i][j]=='T') {
                s[i][j]='.';
                tt.x=i;
                tt.y=j;
            }
            else
             if(s[i][j]!='.')
             update(i,j,s[i][j]);
         }
         printf("Case #%d: %d\n",++f,bfs());
     }
return 0;
}

hdu 5040bfs+优先队列 需要存状态