題意：
? ? ? 給你一個地圖，讓你從起點走到終點，然后圖上有空地，墻，還有攝像頭，攝像頭有初始方向，每一秒攝像頭都會順時針旋轉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; }

總結

以上是生活随笔為你收集整理的hdu5040 不错的广搜旋转的摄像头的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。