題意:
給你一個地圖,讓你從起點走到終點,然後圖上有空地,牆,還有攝像頭,攝像頭有初始方向,每一秒攝像頭都會順時針旋轉90度,每個攝像頭有自己的觀察範圍,它所在的點,和目前它面向的那個點,如果我們目前這一步,和要走的下一步中有一個在目前這個時刻被攝像頭監視着,那麼我們就必須穿上個東西,穿上這個東西之後就可以不被發現了,但是穿上這個東西後移動速度變成每個格子3秒了,或者我們可以選擇目前這一步靜止不動。
思路:
wa了20多次,哎!,對于每一個點最多可以等兩次(有的人說3次),其實就是兩次,因為等兩次之後最快的方式是+1走到下個點,等于直接用3的那個速度直接走過去,我們開一個數組mark[x][y][w] ,表示的是點x,y等待w次時的最優值,然後開個優先隊列(保證第一個出來的答案就是最優的,同時也可以優化時間),然後目前點被監視,或者下一個點被監視的時候,我們就可以原地等待一次。具體看代碼。
#include<stdio.h>
#include<string.h>
#include<queue>
#define N 510
using namespace std;
typedef struct NODE
{
int x ,y ,t ,w;
friend bool operator < (NODE a ,NODE b)
{
return a.t > b.t;
}
}NODE;
NODE xin ,tou;
int mark[N][N][5];
int map[N][N] ,ex ,ey ,n;
int dir[4][2] = {0 ,1 ,0 ,-1 ,1 ,0 ,-1 ,0};
bool ok(int x ,int y)
{
return x >= 1 && x <= n && y >= 1 && y <= n && map[x][y];
}
int sxj(int x ,int y ,int t)
{
if(map[x][y] >= 1 && map[x][y] <= 4) return 1;
if(x - 1 >= 1 && map[x-1][y] >= 1 && map[x-1][y] <= 4)
{
int now = (map[x-1][y] + t) % 4;
if(!now) now = 4;
if(now == 3) return 1;
}
if(x + 1 <= n && map[x+1][y] >= 1 && map[x+1][y] <= 4)
{
int now = (map[x+1][y] + t) % 4;
if(!now) now = 4;
if(now == 1) return 1;
}
if(y - 1 >= 1 && map[x][y-1] >= 1 && map[x][y-1] <= 4)
{
int now = (map[x][y-1] + t) % 4;
if(!now) now = 4;
if(now == 2) return 1;
}
if(y + 1 <= n && map[x][y+1] >= 1 && map[x][y+1] <= 4)
{
int now = (map[x][y+1] + t) % 4;
if(!now) now = 4;
if(now == 4) return 1;
}
return 0;
}
int BFS(int x ,int y)
{
priority_queue<NODE>q;
xin.x = x ,xin.y = y ,xin.t = xin.w = 0;
for(int i = 1 ;i <= n ;i ++)
for(int j = 1 ;j <= n ;j ++)
for(int k = 0 ;k <= 4 ;k ++)
mark[i][j][k] = 100000000;
mark[xin.x][xin.y][xin.w] = 0;
q.push(xin);
while(!q.empty())
{
tou = q.top();
q.pop();
if(tou.x == ex && tou.y == ey) return tou.t;
for(int i = 0 ;i < 4 ;i ++)
{
xin.x = tou.x + dir[i][0];
xin.y = tou.y + dir[i][1];
xin.w = 0;
if(!ok(xin.x ,xin.y)) continue;
if(sxj(tou.x ,tou.y ,tou.t) || sxj(xin.x ,xin.y ,tou.t))
xin.t = tou.t + 3;
else xin.t = tou.t + 1;
if(xin.t < mark[xin.x][xin.y][xin.w])
{
mark[xin.x][xin.y][xin.w] = xin.t;
q.push(xin);
}
}
xin.x = tou.x ,xin.y = tou.y ;
xin.t = tou.t + 1 ,xin.w = tou.w + 1;
if(xin.w <= 2 && xin.t < mark[xin.x][xin.y][xin.w])
{
mark[xin.x][xin.y][xin.w] = xin.t;
q.push(xin);
}
}
return -1;
}
int main ()
{
int t ,i ,j ,x ,y ,cas = 1;
char str[N];
scanf("%d" ,&t);
while(t--)
{
scanf("%d" ,&n);
for(i = 1 ;i <= n ;i ++)
{
scanf("%s" ,str);
for(j = 0 ;j < n ;j ++)
{
if(str[j] == '.') map[i][j+1] = 5;
if(str[j] == '#') map[i][j+1] = 0;
if(str[j] == 'N') map[i][j+1] = 1;
if(str[j] == 'E') map[i][j+1] = 2;
if(str[j] == 'S') map[i][j+1] = 3;
if(str[j] == 'W') map[i][j+1] = 4;
if(str[j] == 'M') map[i][j+1] = 5 ,x = i ,y = j + 1;
if(str[j] == 'T') map[i][j+1] = 5 ,ex = i ,ey = j + 1;
}
}
printf("Case #%d: %d\n" ,cas ++ ,BFS(x ,y));
}
return 0;
}