HDU5040Instrusive

题意：给定一个地图，要从‘M‘点到‘T‘点，每次可以往四个方向移动，平时每次移动1格花费1秒。但是由于地图上有一些监控，如果当前所在格被监控看到，就必须躲在纸箱里，躲在纸箱里移动一格的耗时是3秒。而监控的可视范围是它本身所在的一格，以及它朝向的相邻一格。监控每秒会顺时针旋转90度。地图上还有一些‘#‘标记表示不可以进入的。可以在原地停留1秒。

时间卡得有点紧，单纯dp过不了，要用优先队列优化下

Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1175    Accepted Submission(s): 353

2
3
M..
.N.
..T
3
M.. 
###
..T

Case #1: 5
Case #2: -1

#include<map>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<climits>
#include<list>
#include<iomanip>
#include<stack>
#include<set>
using namespace std;
bool vis[510][510][4];
char pic[510][510];
int tox[4]={-1,1,0,0};
int toy[4]={0,0,-1,1};
int n;
bool light[510][510][4];
struct node
{
	int x,y,t;
	node(){}
	node(int x,int y,int t)
	{
		this->x=x;
		this->y=y;
		this->t=t;
	}
	bool operator <(node one)const
	{
		return t>one.t;
	}
};
int bfs(int x,int y)
{
	priority_queue<node>qq;
	qq.push(node(x,y,0));
	memset(vis,0,sizeof(vis));
	while(qq.size())
	{
		node from=qq.top();
		qq.pop();
		int x=from.x,y=from.y,t=from.t;
		if(vis[x][y][t%4])
			continue;
		vis[x][y][t%4]=1;
		if(pic[x][y]=='T')
			return t;
		if(!vis[x][y][(t+1)%4])
			qq.push(node(x,y,t+1));
		for(int i=0;i<4;i++)
		{
			int nx=x+tox[i],ny=y+toy[i];
			if(nx>=0&&nx<n&&ny>=0&&ny<n)
			{
				if(pic[nx][ny]!='#')
				{
					if(light[x][y][t%4]||light[nx][ny][t%4])
					{
						int nt=t+3;
						if(!vis[nx][ny][nt%4])
							qq.push(node(nx,ny,nt));
					}
					else
					{
						int nt=t+1;
						if(!vis[nx][ny][nt%4])
							qq.push(node(nx,ny,nt));
					}
				}
			}
		}
	}
	return -1;
}
int work()
{
	int sx,sy;
	memset(light,0,sizeof(light));
	for(int t=0;t<4;t++)
		for(int x=0;x<n;x++)
			for(int y=0;y<n;y++)
			{
				if(pic[x][y]=='M')
				{
					sx=x;
					sy=y;
				}
				if(t>0)
				{
					if(pic[x][y]=='N')
						pic[x][y]='E';
					else if(pic[x][y]=='W')
						pic[x][y]='N';
					else if(pic[x][y]=='E')
						pic[x][y]='S';
					else if(pic[x][y]=='S')
						pic[x][y]='W';
				}
				if(pic[x][y]=='N')
				{
					light[x][y][t]=1;
					if(x-1>=0)
						light[x-1][y][t]=1;
				}
				else if(pic[x][y]=='S')
				{
					light[x][y][t]=1;
					if(x+1>=0)
						light[x+1][y][t]=1;
				}
				else if(pic[x][y]=='E')
				{
					light[x][y][t]=1;
					if(y+1<n)
						light[x][y+1][t]=1;
				}
				else if(pic[x][y]=='W')
				{
					light[x][y][t]=1;
					if(y-1>=0)
						light[x][y-1][t]=1;
				}
			}
	return bfs(sx,sy);
}
int main()
{
	int T;
	scanf("%d",&T);
	for(int cs=1;cs<=T;cs++)
	{
		scanf("%d",&n);
		for(int i=0;i<n;i++)
			scanf("%s",pic[i]);
		printf("Case #%d: %d\n",cs,work());
	}
}

HDU5040Instrusive

原文：http://blog.csdn.net/stl112514/article/details/43919761