（北京网络赛09题）题意：给一矩阵（图），里面有起点，终点，还有探照灯（每个有初始朝向，每秒顺时针转90度），前面有灯或者自己被灯照着，移动就要花3秒，求起点到终点最短时间。

用一个数组三维数组记录一下，用来当前位置当前时间%4有没有灯，然后优先队列（时间短的在前面），搜索即可。考虑到可以来回走或者原地等，不能简单判重剪枝：每个地方最多是4种状态！就是4秒之后就全图状态回到一样！所以若当前状态（时间%4）下来过就不用来了。

#include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<cmath>
using namespace std;
struct xy
{
    int x,y;
    int times;
    bool operator <(const xy &ttt)const
    {
        return ttt.times<times;
    }
};
int n;
int a[505][505];
int b[505][505][4];
int vis[505][505][4];
int f[4][2]={-1,0,0,1,1,0,0,-1};
xy ss; int mints;
void bfs()
{
      priority_queue<xy>q;
      q.push(ss);
      while(!q.empty())
      {
          xy cur=q.top();
          q.pop();
          if(a[cur.x][cur.y]==4&&cur.times<mints)
          {
             mints=cur.times;break;
          }
          xy next1=cur;
          next1.times=cur.times+1;
          if(vis[next1.x][next1.y][next1.times%4]==0)
          {
              vis[next1.x][next1.y][next1.times%4]=1;
              q.push(next1);
          }
          for(int i=0;i<4;i++)
          {
              xy next;
               next.x=cur.x+f[i][0];
               next.y=cur.y+f[i][1];
              if(next.x>=0&&next.y>=0&&next.x<n&&next.y<n&&a[next.x][next.y]!=0)
                {
                     if(b[next.x][next.y][cur.times%4]==1||b[cur.x][cur.y][cur.times%4]==1)
                       {

                                next.times=cur.times+3;
                             if(vis[next.x][next.y][next.times%4]==0)
                            {
                                      vis[next.x][next.y][next.times%4]=1;
                                      q.push(next);
                            }
                       }
                       else
                       {
                            next.times=cur.times+1;
                             if(vis[next.x][next.y][next.times%4]==0)
                            {
                                      vis[next.x][next.y][next.times%4]=1;
                                      q.push(next);
                            }
                       }
                }
          }
      }
}
int main()
{
    int T;
     scanf("%d",&T);int cnt=1;
    while(T--)
    {
        scanf("%d",&n);
        memset(b,-1,sizeof(b));
        memset(vis,0,sizeof(vis));
        char tx;char sss[505];
        for(int i=0;i<n;i++)
        {
            scanf("%s",sss);
              for(int j=0;j<n;j++)
             {
                 tx=sss[j];
                if(tx=='.')
                {
                    a[i][j]=1;
                }
                else if(tx=='T')
                {
                    a[i][j]=4;
                }
                else if(tx=='M')
                {
                    a[i][j]=1;
                    ss.x=i;ss.y=j;
                    ss.times=0;
                }
                else if(tx=='#')
                {
                    a[i][j]=0;
                }
                else if(tx=='N')
                {
                    a[i][j]=2;
                     for(int k=0;k<4;k++)
                     {
                         int xx=i+f[k][0];
                         int yy=j+f[k][1];
                         b[i][j][k]=1;
                         if(xx>=0&&yy>=0&&xx<n&&yy<n)
                         {
                             b[xx][yy][k]=1;
                         }
                     }
                }
                else if(tx=='E')
                {
                     a[i][j]=2;
                     for(int k=0;k<4;k++)
                     {
                         int xx=i+f[k][0];
                         int yy=j+f[k][1];
                          b[i][j][k]=1;
                         if(xx>=0&&yy>=0&&xx<n&&yy<n)
                         {
                             int ii=k;
                             if(ii==0)ii=3;
                             else ii--;
                             b[xx][yy][ii]=1;
                         }
                     }
                }
                else if(tx=='S')
                {
                     a[i][j]=2;
                     for(int k=0;k<4;k++)
                     {
                         int xx=i+f[k][0];
                         int yy=j+f[k][1];
                          b[i][j][k]=1;
                         if(xx>=0&&yy>=0&&xx<n&&yy<n)
                         {
                             int ii=k;
                             if(ii==0||ii==1)ii=ii+2;
                             else ii=ii-2;
                             b[xx][yy][ii]=1;
                         }
                     }
                }
                else if(tx=='W')
                {
                     a[i][j]=2;
                     for(int k=0;k<4;k++)
                     {
                         int xx=i+f[k][0];
                         int yy=j+f[k][1];
                          b[i][j][k]=1;
                         if(xx>=0&&yy>=0&&xx<n&&yy<n)
                         {
                             int ii=k;
                             if(ii==3)ii=0;
                             else ii++;
                             b[xx][yy][ii]=1;
                         }
                     }
                }
            }
        }
         mints=0x3f3f3f3f;
        vis[ss.x][ss.y][ss.times]=1;
        bfs();
        printf("Case #%d: ",cnt++);
       if(mints==0x3f3f3f3f)
       {
           printf("-1\n");
       }
       else
       {
           printf("%d\n",mints);
       }
    }
            return 0;
}

hdu 5040 优先队列BFS+剪枝