题意：给n*m的图。图中有一些监视器。如果暴露在监视器下就会被发现。但是他有一个卡片盒子，他能躲在卡片盒子中，在卡片盒子中到下一个点需要花费3个单位的时间，如果不在卡片盒子中走到下一个点需要1个单位的时间，每个监视器可以监视的范围为它本身和四周的一个格子(上下左右)。如果一个点正在被监视。那么只能藏在盒子里走过去。他能在盒子里走到正在被监视的格子。每个监视器一开始监视某个格子，然后每秒顺时针旋转九十度。
这个图中包含
. 空地
# 障碍物
N 朝向北
S 朝向南
W 朝向西
E 朝向东
M 起始点
T 目标点
做法：暴搜，判断一个点在某个时间是否正在被监视比较麻烦。但是可以特殊处理。可以根据step%4的值来判断。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits.h>
using namespace std;
typedef long long LL;
const int MAXN=510;
int t,cas=0,n,m;
char map1[MAXN][MAXN];
int vis[MAXN][MAXN];
char stat[MAXN][MAXN];
struct point {
int x,y,step,stat;
bool operator<(point x)const {
return step>x.step;
}
}st,et;
int dx[]={-1,0,1, 0};
int dy[]={ 0,1,0,-1};
bool checkpoint(int x,int y,int step){
for(int i=0;i<4;i++){
if(((stat[x][y]>>i)&1)&&step%4==i)return true;
}
return false;
}
int bfs(){
priority_queue <point> q;
point now,next;
memset(vis,-1,sizeof(vis));
vis[st.x][st.y]=0;
q.push(st);
while(!q.empty()){
now=q.top();
q.pop();
if(checkpoint(now.x,now.y,now.step)){
now.stat=1;
}
else now.stat=0;
for(int i=0;i<4;i++){
next.x=now.x+dx[i];
next.y=now.y+dy[i];
next.stat=now.stat;
if(next.x<1||next.x>n||next.y<1||next.y>m)continue;
if(map1[next.x][next.y]=='#')continue;
if(now.stat||checkpoint(next.x,next.y,now.step)){
if(!checkpoint(now.x,now.y,now.step+1)&&
!checkpoint(next.x,next.y,now.step+1)){
next.step=now.step+2;
}
else {
next.step=now.step+3;
}
}
else next.step=now.step+1;
if(vis[next.x][next.y]==-1||next.step<vis[next.x][next.y]){
vis[next.x][next.y]=next.step;
q.push(next);
}
}
}
return vis[et.x][et.y];
}
int main()
{
scanf("%d",&t);
while(t--){
scanf("%d",&n);
m=n;
memset(stat,0,sizeof(stat));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf(" %c",&map1[i][j]);
if(map1[i][j]=='M'){
st.x=i;st.y=j;
st.step=0;st.stat=0;
}
if(map1[i][j]=='T'){
et.x=i;et.y=j;
}
if(map1[i][j]=='N'){
stat[i][j]=0xf;
for(int k=0;k<4;k++){
int tx=i+dx[k];
int ty=j+dy[k];
stat[tx][ty]|=(1<<k);
}
}
if(map1[i][j]=='E'){
stat[i][j]=0xf;
for(int k=1;k<5;k++){
int tk=k%4;
int tx=i+dx[tk];
int ty=j+dy[tk];
stat[tx][ty]|=(1<<(k-1));
}
}
if(map1[i][j]=='S'){
stat[i][j]=0xf;
for(int k=2;k<6;k++){
int tk=k%4;
int tx=i+dx[tk];
int ty=j+dy[tk];
stat[tx][ty]|=(1<<(k-2));
}
}
if(map1[i][j]=='W'){
stat[i][j]=0xf;
for(int k=3;k<7;k++){
int tk=k%4;
int tx=i+dx[tk];
int ty=j+dy[tk];
stat[tx][ty]|=(1<<(k-3));
}
}
}
}
printf("Case #%d: %d\n",++cas,bfs());
}
scanf(" ");
return 0;
}
|
