題目描述

2011年3月16日以來，利比亞爆發的騷亂不斷升級，已嚴重危及到普通民眾和各國在利比亞工作的人員的安全。為了盡快救出在利比亞的同胞，根據利比亞的形勢，我國政府告訴每個在利比亞的公民，如何行動才能最快地到達安全的地方，然后由我國派出的飛機、輪船、汽車接回國。假設將利比亞的地圖劃分為一個n行m列的長方形，待拯救的同胞小A在1行1列處，安全的目標位置在n行m列處。利比亞是一個多沙漠的國家，經過某些位置需要消耗一定數量的食品，某些位置存儲有很多很多食品。假定小A現在在位置i行j列，如果身上帶有足夠在新位置處需要消耗的食品的話，小A的下一個位置將到達i-1行j列、i+1行j列、i行j-1列、i行j+1列這四個位置之一，如果新位置處有食品的話，小A最多能拿一份該位置處的食品。當然如果小A已有的食品加上新位置處的一份食品數量超過小A能帶食品的最高上限，小A就不能拿該位置處的食品了。如果身上的食品不夠到下一位置處的消耗，小A就不能到下一位置去，否則會面臨生命危險的。當然，小A可以數次經過同一個位置，每次到此位置，都需要先消耗食品，然后可以拿一份食品（如果有的話）,也就是小A可以多次到同一個地方來攢食品,也可以多次到同一個地方來消耗食品。若一個位置既要消耗食品,又可以拿食品，則小A必須先消耗食品,然后才能拿一份食品。給出利比亞的地圖,請告訴小A如何最快地從起點(1,1)走到終點(n,m)。程序只要輸出最短路徑長度就可以了。

輸入

輸入文件libyan.in的第一行有4個正整數n,m,t,maxc(1≤n≤200，1≤m≤200，0≤t≤maxc≤270)，它們之間以一個空格分隔。表示利比亞的地形可以分為n行m列，小A一開始時的食品數量為t，身上最多能帶maxc的食品。
接下來n行,每行m個字符,分別表示地圖中該位置的信息。其中：
字符“”表示這個位置是建筑物、河流、有地雷等人無法走到的位置（保證起點終點不是“”）;
數字字符“1”~“9”表示這個位置有該數量的食品;
小數點“.”表示人可以走到該位置，但該位置沒有食品。
第n+2行只有一個正整數k，表示到達這k個位置會消耗食品。接下來k行,每行三個正整數x,y,w，表示每次到第x行y列處會消耗數量為w的食品。數據保證同一個位置不會出現兩次。

輸出

輸出文件libyan.out只有一行，該行只有一個正整數。表示小A從起點到終點，在保證自身安全情況下走過的最短路徑長度。

樣例輸入

樣例輸入1

3 5 0 0
.*…
…*.
...
0

樣例輸入2

4 5 2 5
..*.1
1.*..
*.1..
….1
4
1 2 2
3 2 1
4 2 3
4 3 3

樣例輸出

樣例輸出1

8

樣例輸出2

7

數據范圍限制

70%的數據中，沒有需要消耗食品的地方和存儲有食品的地方。即在這些70%的數據中,輸入的t=0,maxc=0,k=0,n行m列輸入的地圖只有小數點和*二種字符。
在上述70%的數據中,其中有40%的數據n,m均不超過100。

思路：

記憶化寬搜，開N大的數組…………

代碼：

vara:array[0..201,0..201]of char;na,xiao:array[0..201,0..201]of longint;c:array[1..4,1..2]of longint=((-1,0),(0,1),(1,0),(0,-1));st:string;f:array[0..201,0..201,0..271]of longint;d:array[0..1000001,1..4]of longint;n,m,i,j,k,x,y,z,s,ls,t,o,x1,y1:longint; function min(x,y:longint):longint; beginif x<y then exit(x)else exit(y); end; beginassign(input,'libyan.in');reset(input);assign(output,'libyan.out');rewrite(output);readln(n,m,x,t);for i:=1 to n dobeginreadln(st);for j:=1 to m doif (st[j]>='0')and(st[j]<='9') thenbegina[i,j]:='.';na[i,j]:=ord(st[j])-48;endelse a[i,j]:=st[j];end;readln(o);for i:=1 to o dobeginreadln(x1,y1,z);xiao[x1,y1]:=z;end;d[1,1]:=1;d[1,2]:=1;d[1,3]:=x;d[1,4]:=0;i:=0;j:=1;while i<j dobegininc(i);for k:=1 to 4 doif (d[i,1]+c[k,1]>0)and(d[i,1]+c[k,1]<=n)and(d[i,2]+c[k,2]>0)and(d[i,2]+c[k,2]<=m)and(a[d[i,1]+c[k,1],d[i,2]+c[k,2]]<>'*') thenbeginx1:=d[i,1]+c[k,1];y1:=d[i,2]+c[k,2];if d[i,3]>=xiao[x1,y1] thenbeginz:=d[i,3]+na[x1,y1]-xiao[x1,y1];z:=min(z,t);if (f[x1,y1,z]=0)or(f[x1,y1,z]>d[i,4]+1) thenbeginf[x1,y1,z]:=d[i,4]+1;inc(j);d[j,1]:=x1;d[j,2]:=y1;d[j,3]:=z;d[j,4]:=d[i,4]+1;if (x1=n)and(y1=m) thenbeginwriteln(d[j,4]);halt;end;end;end;end;end; end.

總結

以上是生活随笔為你收集整理的利比亚行动的全部內容，希望文章能夠幫你解決所遇到的問題。

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