HDU5040-Instrusive （優先隊列+BFS）

The legendary mercenary Solid Matt gets a classic mission: infiltrate a military base.

The military base can be seen as an N * N grid. Matt’s target is in one of the grids and Matt is now in another grid.

In normal case, Matt can move from a grid to one of the four neighbor grids in a second. But this mission is not easy.

Around the military base there are fences, Matt can’t get out of the base.

There are some grids filled with obstacles and Matt can’t move into these grids.

There are also some surveillance cameras in the grids. Every camera is facing one of the four direction at first, but for every second, they will rotate 90 degree clockwisely. Every camera’s sight range is 2, which means that if Matt is in the same grid as the camera, or in the grid that the camera is facing, he will be seen immediately and the mission will fail.

Matt has a special equipment to sneak: a cardbox. Matt can hide himself in the card box and move without being noticed. But In this situation, Matt will have to use 3 seconds to move 1 grid. Matt can also just hide in the cardbox without moving. The time to hide and the time to get out of the cardbox can be ignored.

Matt can’t take the risk of being noticed, so he can’t move without cardbox into a grid which is now insight of cameras or from a grid which is now insight of cameras. What’s more, Matt may be in the cardbox at the beginning.

As a live legend, Matt wants to complete the mission in the shortest time.

Input

The first line of the input contains an integer T, denoting the number of testcases. Then T test cases follow.

For each test cases, the first line contains one integer:N(1<=N<=500)

In the following N lines, each line contains N characters, indicating the grids.

There will be the following characters:

● ‘.’ for empty

● ‘#’ for obstacle

● ‘N’ for camera facing north

● ‘W’ for camera facing west

● ‘S’ for camera facing south

● ‘E’ for camera facing east

● ‘T’ for target

● ‘M’ for Matt

Output

For each test case, output one line “Case #x: y”, where x is the case number (starting from 1) and y is the answer.

If Matt cannot complete the mission, output ‘-1’.

Sample Input

2

3

M..

.N.

..T

3

M..

#

..T

Sample Output

Case #1: 5

Case #2: -1

題目：HUD5040

題意：給定一張圖：

.-空地

#-牆

W,N,S,E-錄影機，以及錄影機第一秒所面對的方向

M-起點

T-終點

M執行任務要從起點到終點，但是地圖上有一些錄影機，M在錄影機下走一格需要3S，在空地（.）上走一格需要1S，錄影機有一個初始朝向，此後每秒，錄影機順時針轉動90°，錄影機的監視範圍為錄影機所在位置以及向面朝的方向延伸1格。

思路：根據題意，我們可以先把地圖處理成四張子圖，每張子圖對應time%4時地圖的狀态，然後暴力搜尋即可，注意，題目允許M待在原地，并且當M在錄影機下或者M走的下一步在錄影機下，花費的時間都應該為3S，标記時，我們對每個格子的4中狀态分别标記即可。

忠告：不要修改原圖，盡量開4張新圖，記憶體不要錢啊，使勁造，不然BUG找到死。。。。

AC代碼：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#define met(s,k) memset(s,k,sizeof s)
#define scan(a) scanf("%d",&a)
#define scanl(a) scanf("%lld",&a)
#define scann(a,b) scanf("%d%d",&a,&b)
#define scannl(a,b) scanf("%lld%lld",&a,&b)
#define scannn(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define prin(a) printf("%d\n",a)
#define prinl(a) printf("%lld\n",a)
using namespace std;
typedef long long ll;
int dir[][]= {-,,,,,,,-};
int n,sx,sy,ex,ey;
char mp[][][],mmp[][];
int ss[][][];
struct node
{
    int x,y,t;
    friend bool operator< (node a,node b)
    {
        return a.t>b.t;
    }
};
int judge(int x,int y)
{
    if(x>=&&x<n&&y>=&&y<n)return ;
    return ;
}
void car(int i,int j)
{
    if(mmp[i][j]=='E')
    {
        mp[][i][j]=mp[][i][j]=mp[][i][j]=mp[][i][j]='*';
        if(judge(i,j+))mp[][i][j+]='*';
        if(judge(i+,j))mp[][i+][j]='*';
        if(judge(i,j-))mp[][i][j-]='*';
        if(judge(i-,j))mp[][i-][j]='*';
    }
    else if(mmp[i][j]=='S')
    {
        mp[][i][j]=mp[][i][j]=mp[][i][j]=mp[][i][j]='*';
        if(judge(i,j+))mp[][i][j+]='*';
        if(judge(i+,j))mp[][i+][j]='*';
        if(judge(i,j-))mp[][i][j-]='*';
        if(judge(i-,j))mp[][i-][j]='*';
    }
    else if(mmp[i][j]=='W')
    {
        mp[][i][j]=mp[][i][j]=mp[][i][j]=mp[][i][j]='*';
        if(judge(i,j+))mp[][i][j+]='*';
        if(judge(i+,j))mp[][i+][j]='*';
        if(judge(i,j-))mp[][i][j-]='*';
        if(judge(i-,j))mp[][i-][j]='*';
    }
    else if(mmp[i][j]=='N')
    {
        mp[][i][j]=mp[][i][j]=mp[][i][j]=mp[][i][j]='*';
        if(judge(i,j+))mp[][i][j+]='*';
        if(judge(i+,j))mp[][i+][j]='*';
        if(judge(i,j-))mp[][i][j-]='*';
        if(judge(i-,j))mp[][i-][j]='*';
    }
}
int bfs()
{
    node now,next;
    now.x=sx;
    now.y=sy;
    now.t=;
    priority_queue<node>q;//優先隊列，保證答案最小
    q.push(now);
    while(q.size())
    {
        now=q.top();
        if(now.x==ex&&now.y==ey)return now.t;
        next=now;
        next.t++;
        if(!ss[next.t%4][next.x][next.y])ss[next.t%4][next.x][next.y]=,q.push(next);
        for(int i=; i<; i++)
        {
            next.x=now.x+dir[i][];
            next.y=now.y+dir[i][];
            if(judge(next.x,next.y)&&mmp[next.x][next.y]!='#')
            {
                if(mp[now.t%4][now.x][now.y]=='*'||mp[now.t%4][next.x][next.y]=='*')next.t=now.t+;//如果目前，或者下一步在監視範圍裡，花費S
                else next.t=now.t+;
                if(!ss[next.t%4][next.x][next.y])
                {
                    ss[next.t%4][next.x][next.y]=;
                    q.push(next);
                }
            }
        }
        q.pop();
    }
    return -;
}
int main()
{
    int t;
    scan(t);
    for(int cas=; cas<=t; cas++)
    {
        scan(n);
        met(ss,);
        met(mp,);
        for(int i=; i<n; i++)scanf("%s",mmp[i]);
        for(int i=; i<n; i++)
        {
            for(int j=; j<n; j++)
            {
                if(mmp[i][j]=='M')sx=i,sy=j,mmp[i][j]='.';
                else if(mmp[i][j]=='T')ex=i,ey=j,mmp[i][j]='.';
                else if(mmp[i][j]!='.'&&mmp[i][j]!='#')car(i,j);//存圖
            }
        }
        printf("Case #%d: %d\n",cas,bfs());
    }
    return ;
}