WA到死的一道题目。

一个人从起点走到目标点。这个过程中有摄像头，摄像头的照射范围为两个单位长度，包括摄像头自己的位置。为了避免被照射到，可以有两种选择。

在一个位置等待1S，或者坐在盒子里过去（花费3S），走一步花费1S。摄像头每秒顺时针转一次。

1.4S有一个循环，所以每个位置vis[r][c][sec] 四种情况的最优解

2.不用显示构图， 每个摄像头都记录一下四种情况

3.使用优先队列，判断

RE,TLE,WA,AC.....

刚开始每个摄像头旋转的时候没有判断是否在范围内，一直RE，起初没考虑到当前是摄像头的情况也可以有三步或者等待情况。起初认为摄像头位置不可进入，其实可以的。。WA到死。

BFS所选择的路径必然是最优的（每次不断扩展）

NOTICE: 注意判断一个状态的元素，是否在范围内。

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<memory.h>
#include<queue>
#define max(a,b) (a)>(b)?(a):(b)
#define min(a,b) (a)<(b)?(a):(b)
#define PI acos(-1)
#define INF 100000

using namespace std;
typedef __int64 LL;
const LL maxn=10+500;
using namespace std;

struct P
{
	int row,col;
	int step;//direct
}st,ed;
struct cmp{
    bool operator() ( struct P a, struct P b ){
        return a.step> b.step;
    }
};
int N,M,T,Q,POS;
int ans,tot;
int vis[maxn][maxn][4];
int done[maxn][maxn][4];
int map1[maxn][maxn];
int maps[4][maxn][maxn];
int turn[4][2]={   {0,-1},{1,0},{0,1}  ,{-1,0}  };
struct P monitor[maxn*maxn];
int monnum;

int In(int x,int y)
{
	if(x<0 ||x>=N || y<0 || y>=N)
		return 0;
	return 1;
}

void change(int sec,int (*map1)[maxn])
{
	int i,k;
	struct P t;
	for(i=0;i<monnum;i++)
	{
		t=monitor[i];
		k=(t.step+sec)%4;
		t.row+=turn[k][1];
		t.col+=turn[k][0];
		if(In(t.row,t.col) && map1[t.row][t.col]==0)
			map1[t.row][t.col]=2;
	}
	//print(map1);
}
void bfs()
{
	int i,j,k;int xx,yy;
	memset(vis,0x3f,sizeof(vis));//存储最短路径
	memset(done,0,sizeof(vis));//是否访问过，从优先队列中取出的必然是最短的
	priority_queue<struct P,vector<struct P>,cmp>q;
	struct P t,tt;
	q.push(st);//vis[st.row][st.col][0]=-1;
	while(!q.empty())
	{
		t=q.top();
		q.pop();
		int sec=(t.step)%4;
		if(done[t.row][t.col][sec])
			continue;
		done[t.row][t.col][sec]=1;
		
		for(i=0;i<4;i++)
		{
			xx=t.col+turn[i][0];
			yy=t.row+turn[i][1];
			if(xx<0 || yy<0 || xx>=N || yy>=N || maps[sec][yy][xx]==1)
				continue;
			tt.row=yy;
			tt.col=xx;
			int w=1;
			if(maps[sec][yy][xx]==2 || maps[sec][t.row][t.col]==2)
				w=3;
			if(vis[yy][xx][(sec+w)%4]>t.step+w)
			{
				tt.step=t.step+w;
				vis[yy][xx][(sec+w)%4]=t.step+w;
				q.push(tt);	
			}	
		}
		if(vis[t.row][t.col][(sec+1)%4]>t.step+1)
		{
			t.step++;
			vis[t.row][t.col][(sec+1)%4]=t.step;
			q.push(t);
			t.step--;
		}
	}
	ans=INF;
	for(i=0;i<4;i++)
		if(vis[ed.row][ed.col][i])
			ans=min(ans,vis[ed.row][ed.col][i]);
}

int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
#endif
	int i,j,len,cnt=0;
	char str[1000];
	scanf("%d",&T);
	while(T--)
	{
		
		scanf("%d",&N);getchar();
		monnum=0;memset(map1,0,sizeof(map1));
		for(i=0;i<N;i++)
		{
			gets(str);
			len=strlen(str);
			for(j=0;j<len;j++)
			{
				if(str[j]=='#')
					map1[i][j]=1;
				else if(str[j]=='M')
				{
					st.col=j;
					st.row=i;
					st.step=0;
				}
				else if(str[j]=='T')
				{
					ed.col=j;
					ed.row=i;
					ed.step=0;
				}
				else if(str[j]=='N')
				{
					map1[i][j]=2;
					monitor[monnum].col=j;
					monitor[monnum].row=i;
					monitor[monnum].step=0;monnum++;
				}
			 else if(str[j]=='E')
                {
                    map1[i][j]=2;
                    monitor[monnum].col=j;
                    monitor[monnum].row=i;
                    monitor[monnum].step=1;monnum++;
                }
                else if(str[j]=='S')
                {
                    map1[i][j]=2;
                    monitor[monnum].col=j;
                    monitor[monnum].row=i;
                    monitor[monnum].step=2;monnum++;
                }
                else if(str[j]=='W')
                {
                    map1[i][j]=2;
                    monitor[monnum].col=j;
                    monitor[monnum].row=i;
                    monitor[monnum].step=3;monnum++;
                }
            }
        }
        for(i=0;i<4;i++)//显示构图，很花费时间
        {
            memcpy(maps[i],map1,sizeof(map1));
            change(i,maps[i]);
        }
		bfs();
        if(ans==INF) ans=-1;
        printf("Case #%d: %d\n",++cnt,ans);
    }
    return 0;
}

再贴一个中山大学的，神代码

#include <stdio.h>
#include <string.h>
#include <queue>

using namespace std;

const int MAXN = 510;
int n;
char s[MAXN][MAXN];
int x0, y0;
int d0[MAXN][MAXN];
struct state {
    int x, y, t, k;
    state(int x, int y, int t, int k): x(x), y(y), t(t), k(k) {}
};
bool v[MAXN][MAXN][3];
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

void init()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%s", s[i]);
        for (int j = 0; j < n; ++j) {
            switch (s[i][j]) {
                case 'N': d0[i][j] = 0; break;
                case 'E': d0[i][j] = 1; break;
                case 'S': d0[i][j] = 2; break;
                case 'W': d0[i][j] = 3; break;
                default: d0[i][j] = -1; break;
            }
            if (s[i][j] == 'M') x0 = i, y0 = j;
        }
    }
}

inline bool inrange(int x, int y)
{
    return x >= 0 && x < n && y >= 0 && y < n;
}

bool capture(int x, int y, int t)
{
    if (d0[x][y] >= 0) return true;
    for (int i = 0; i < 4; ++i) {
        int nx = x - dx[i], ny = y - dy[i];
        if (inrange(nx, ny) && d0[nx][ny] >= 0) {
            if ((d0[nx][ny] + t) % 4 == i) return true;
        }
    }
    return false;
}

void push(queue<state> &q, int x, int y, int t, int k)
{
    if (!v[x][y][k]) {
        q.push(state(x, y, t, k));
        v[x][y][k] = true;
    }
}

int bfs(int x, int y)
{
    memset(v, 0, sizeof(v));
    queue<state> q;
    push(q, x, y, 0, 0);
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int t = q.front().t;
        int k = q.front().k;
        // printf("%d %d %d %d\n", x, y, t, k);
        q.pop();
        if (k) {
            if (k == 1 && s[x][y] == 'T') return t + 1;
            push(q, x, y, t + 1, k - 1);
            continue;
        }
        bool f = capture(x, y, t);
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (!inrange(nx, ny) || s[nx][ny] == '#') continue;
            if (f || capture(nx, ny, t)) {
                for (int j = 1; j <= 2; ++j) {
                    if (j == 2 || (!capture(x, y, t + j) && !capture(nx, ny, t + j))) {
                        push(q, nx, ny, t + 1, j);
                        break;
                    }
                }
            } else {
                if (s[nx][ny] == 'T') return t + 1;
                push(q, nx, ny, t + 1, 0);
            }
        }
    }
    return -1;
}

int main()
{
    int dat;
    scanf("%d", &dat);
    for (int cas = 1; cas <= dat; ++cas) {
        init();
        printf("Case #%d: %d\n", cas, bfs(x0, y0));
    }
}

2014 ACM/ICPC Asia Regional Beijing Online HDU 5040 Instrusive 优先队列