伊吹萃香(Ibuki Suika)正在魔法之森漫步，突然，許多西瓜(Suika)從四周飛來，劃出了絢麗的軌跡。雖然陣勢有點恐怖，但她還是決定抱走一些西瓜。

題目描述

萃香所處的環境被簡化為一個長為h，寬為w的網格平面。X坐標范圍為[1,w]，y坐標范圍為[1,h]。

她初始（第1個時刻）站在坐標為sx,sy的方格。

西瓜可能在任意一個方格出現，在每個時間單位，它們可能向任何一個方向移動，也可能靜止不動。西瓜的位置和移動的軌跡是已知的。西瓜的總數為n個，但只有m個西瓜可以被萃香抱走，因為其他都太大了，可能會砸傷她。

整個過程會持續T個時刻。萃香希望可以抱走全部的m個西瓜，并且在任何時候避免與任何一個過大的西瓜處在同一位置。抱走的方式為在某個時刻，與該西瓜處于同一位置。另外，由于萃香不愿耗費過多體力到處亂跑，她每個時刻可以選擇靜止不動，也可以選擇移動到相鄰的四個格子之一，只要不越出環境邊界。如果選擇移動到相鄰格子，則算作移動了一次。(第1個時刻萃香剛站定，無法移動)

在每個時刻，如果萃香選擇移動，可以認為萃香與西瓜同時從原來的位置移到了新的位置，沒有先后順序。

萃香想要知道，不被任何一個大西瓜砸中，并得到所有的m個小西瓜的情況下，最少需要移動多少次。

輸入輸出格式

輸入格式：

第一行五個整數h,w,T,sx,sy，含義見題目描述。

第二行兩個整數n,m，含義見題目描述。

接下來n段數據，每一段描述了一個西瓜的出現位置，時間，移動方式，是否可以被抱走等內容，具體如下:

首先一行，兩個整數t1,t2，表示西瓜在t1時刻出現， t2時刻消失。若t2=T+1,表示西瓜在最后一個時刻也不消失。保證西瓜至少存在一個時刻。

接下來一行一個整數a,只能為0或1,0表示這個西瓜需要避開，1表示這個西瓜需要抱走。數據保證需要抱走的西瓜恰好有m個。

接下來t2-t1行，每一行兩個整數x,y，順序描述了從t1時刻到t2-1時刻，該西瓜的坐標。西瓜的移動不一定是連續的，并且是一瞬間完成的，所以無需考慮萃香是否站在了移動路徑上。

輸出格式：

如果萃香在整個T時刻內無法避免被大西瓜砸中或者無法收集到所有m個小西瓜，輸出-1,否則輸出一個整數，表示萃香需要移動的最少次數。

輸入輸出樣例

輸入樣例#1：
5 5 10 3 3 1 1 1 11 1 3 4 5 2 3 5 1 1 5 4 3 4 2 1 1 1 1 1 5 5 輸出樣例#1：
1

說明

樣例說明:第2~4個時刻萃香站著不動，在第6個時刻，西瓜出現在萃香旁邊，萃香移動到(3,4)位置即可抱走這個西瓜。

數據范圍和提示:

子任務可能出現兩種特殊性質A和B

A: 所有西瓜t1=1,t2=T+1

所有西瓜全程都靜止在原地，不會發生移動。

B：m=0

共有10個子任務。

對于子任務1，具有特殊性質A和B

對于子任務2~3，僅具有特殊性質A

對于子任務4~5，僅具有特殊性質B

對于子任務6~10，不具有任何一個特殊性質。

對于全部子任務

1<=所有橫坐標范圍<=w 1<=所有縱坐標范圍<=h 1<=h,w<=5 1<=T<=100 1<=t1<=T 2<=t2<=T+1 t1<t2 1<=n<=20 0<=m<=10 m<=n

一個位置不會同時出現兩個或以上西瓜。

子任務1:所有西瓜始終出現且不動，并且沒有要抱走的。

?

解法:只需要判斷初始位置是否被大西瓜擋住，擋住輸出-1，否則輸出0即可

?

子任務2~3:所有西瓜始終出現且不動。

?

解法:由于要抱走的西瓜最多為10個，考慮用長度為10的0/1串來表示某個西瓜是否已經獲取。狀壓spfa或dp即可解決。

?

子任務4~5:沒有需要抱走的西瓜

?

解法:將時間看做一個維度，構建好三維的地圖，把西瓜看做障礙，做三維的最短路或dp即可。

正解：bfs+狀態壓縮dp

狀態轉移：dist[x'][y'][t][k']=min(dist[x][y][t-1][k])

dist[x][y][t][k]表示在(x,y),t時，取西瓜的狀態k，k為一個二進制數

事先處理出(x,y),t時有無西瓜，是哪個西瓜。

接下來就是bfs過程的實現

注意的是這里用了一個小技巧：

當所要記錄的狀態有多個，且都很小時，可以把它們分配在一個數的不同位，用一個數表示。如123/456/7/8表示(7,8)時t=456，k為123的二進制

?

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 using namespace std; 6 int mp[6][6][103]; 7 int dist[6][6][103][1024]; 8 bool vis[6][6][103][1024]; 9 const int dx[5]={0,1,-1,0,0}; 10 const int dy[5]={0,0,0,1,-1}; 11 int w,h,T,sx,sy,cnt; 12 int n,m; 13 queue<int> q; 14 void spfa() 15 { 16 q.push(1*100+sx*10+sy); 17 memset(dist,0x3f,sizeof(dist)); 18 dist[sx][sy][1][0]=0; 19 while(!q.empty()) 20 { 21 int now=q.front(); 22 q.pop(); 23 int nows=now/100000; 24 int nowt=(now%100000)/100; 25 int nowx=(now%100)/10; 26 int nowy=now%10; 27 //cout<<nowx<<' '<<nowy<<endl; 28 vis[nowx][nowy][nowt][nows]=0; 29 if (nowt==T) 30 continue; 31 for (int i=0;i<=4;i++) 32 { 33 int nextx=nowx+dx[i]; 34 int nexty=nowy+dy[i]; 35 int nextt=nowt+1; 36 int nexts; 37 if (nextx<1||nextx>w) continue; 38 if (nexty<1||nexty>h) continue; 39 if (mp[nextx][nexty][nextt]==10000) continue; 40 if (mp[nextx][nexty][nextt]==0x3f3f3f3f) nexts=nows; 41 else 42 { 43 nexts=nows|(1<<(mp[nextx][nexty][nextt]-1)); 44 } 45 if (dist[nowx][nowy][nowt][nows]+(bool)(i)<dist[nextx][nexty][nextt][nexts]) 46 { 47 dist[nextx][nexty][nextt][nexts]=dist[nowx][nowy][nowt][nows]+(bool)(i); 48 if (vis[nextx][nexty][nextt][nexts]==0) 49 { 50 vis[nextx][nexty][nextt][nexts]=1; 51 q.push(nexts*100000+nextt*100+nextx*10+nexty); 52 } 53 } 54 } 55 } 56 } 57 int main() 58 { 59 scanf("%d%d%d%d%d",&w,&h,&T,&sx,&sy); 60 scanf("%d%d",&n,&m); 61 memset(mp,0x3f,sizeof(mp)); 62 for(int i=1;i<=n;i++) 63 { 64 int t1,t2,a; 65 scanf("%d%d",&t1,&t2); 66 scanf("%d",&a); 67 if(a==0)a=10000; 68 else a=++cnt; 69 for(int i=t1;i<t2;i++) 70 { 71 int x,y; 72 scanf("%d%d",&x,&y); 73 mp[x][y][i]=a; 74 } 75 } 76 if(mp[sx][sy][1]==10000) 77 { 78 printf("-1\n"); 79 return 0; 80 } 81 spfa(); 82 int ans=0x3f3f3f3f; 83 for(int i=1;i<=w;i++) 84 for(int j=1;j<=h;j++) 85 ans=min(ans,dist[i][j][T][(1<<m)-1]); 86 if(ans==0x3f3f3f3f)ans=-1; 87 printf("%d\n",ans); 88 return 0; 89 }

?

轉載于:https://www.cnblogs.com/Y-E-T-I/p/7121985.html

總結

以上是生活随笔為你收集整理的萃香抱西瓜的全部內容，希望文章能夠幫你解決所遇到的問題。

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