hdu 5040 bfs

http://acm.hdu.edu.cn/showproblem.php?pid=5040
한 사람 이 종이 상 자 를 들 고 목적지 로 가다  정상 적 인 상황 에서 1 초 에 한 칸 씩 가요.  제자리 에서 움 직 이지 않 고 상자 안에 숨 어도 돼 요.  상 자 를 끼 고 3 초 에 한 칸 씩 걸 을 수도 있어 요. 
지도 에 등불 이 좀 있다.  등 은 자신 과 앞 칸 을 비 출 수 있다.  매 초 등 은 시계 방향 으로 90 도 돈다.  불 이 비 치 는 곳 에서 떠 나 거나 불 이 비 치 는 곳 으로 들 어 가 려 면 반드시 상 자 를 채 워 야 한다. 
최 단 시간 에 도착 하 다
제목 이 불분명 한 bfs

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <bitset>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define clr0(x) memset(x,0,sizeof(x))
typedef long long LL;
const int maxn = 505;
int sx,sy,n;
int dx[] = {0,1,0,-1},
    dy[] = {1,0,-1,0};
char s[maxn][maxn];
int dirr[128],notic[maxn][maxn];
bool vis[maxn][maxn][4];
bool in(int x,int y)
{
    return 0 <= x && x < n && 0 <= y && y < n;
}
struct node{
    int t,x,y;
    bool operator < (const node &a)const{
        return t > a.t;
    }
};
int bfs()
{
    priority_queue <node> q;
    q.push((node){0,sx,sy});
    while(!q.empty()){
        node now = q.top(),to;
        q.pop();
        if(s[now.x][now.y] == 'T'){
            return now.t;
        }
        if(vis[now.x][now.y][now.t%4])   continue;
        vis[now.x][now.y][now.t%4] = true;
        to = now,to.t++;
        q.push(to);
        for(int i = 0;i < 4;++i){
            int mx = now.x + dx[i],my = now.y + dy[i];
            if(in(mx,my) && s[mx][my] != '#'){
                //                       
                to.t = now.t + 1;
                if( (notic[mx][my] | notic[now.x][now.y]) & (1<<(now.t%4)) )
                    to.t = now.t + 3;
                to.x = mx,to.y = my;
                q.push(to);
            }
        }
    }
    return -1;
}
int main (){
    int  _,cas = 1;
    RD(_);
    dirr['E'] = 0,dirr['S'] = 1,dirr['W'] = 2,dirr['N'] = 3;
    dirr['T'] = dirr['M'] = dirr['.'] = dirr['#'] = -1;
    while(_--){
        printf("Case #%d: ",cas++);
        RD(n);
        clr0(notic);
        clr0(vis);
        for(int i = 0;i < n;++i){
            scanf("%s",s[i]);
            for(int j = 0;j < n;++j){
                if(s[i][j] == 'M')
                    sx = i,sy = j;
                else{
                    int now = dirr[ s[i][j] ];
                    if(now == -1)
                        continue;
                    notic[i][j] = (1<<4) - 1;
                    for(int k = now;k < 4+now;++k){
                        int mx = i + dx[k%4],my = j + dy[k%4];
                        if(in(mx,my)){
                            notic[mx][my] |= (1<<(k-now));
                        }
                    }
                }
            }
        }
        cout<<bfs()<<endl;
    }
    return 0;
}