Description

設(shè)有一個n×m(小于100)的方格（如圖所示），在方格中去掉某些點，方格中的數(shù)字代表距離（為小于100的數(shù)，如果為0表示去掉的點），試找出一條從A(左上角)到B（右下角）的路徑，經(jīng)過的距離和為最小（此時稱為最小代價），從A出發(fā)的方向只能向右，或者向下。

Sample Input

4 4
4 10 7 0
3 2 2 9
0 7 0 4
11 6 12 1
Sample Output

(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)
24

---

首先現(xiàn)將最上面那行和最左邊那行定初值。
用f[i,j]來判斷這個點是否為0如果為0，則為TRUE。
那么我們就可以用兩重循環(huán)，來枚舉行和列。如果這個點可以走，那就判斷是從上面走下來比較下，還是從左邊走過來比較小。還要判斷左邊或上面是否為0。
f[i,j]:=max(f[i-1,j]+a[i,j]，f[i,j-1]+a[i,j]);
如果從上面來，則d[i,j]=2;從左來則為1。
最后倒推回去，找到路線和最終的最小代價值。

---

代碼如下：

var  i,j,n,m:longint;a,k,d:array[-1..101,-1..101]of longint;f:array[-1..101,-1..101]of boolean;procedure dg(x,y:longint);
beginif (x=1)and(y=1) then begin write('(',x,',',y,')'); exit; end;if d[x,y]=1 then dg(x,y-1) else dg(x-1,y);write('->(',x,',',y,')');
end;beginreadln(n,m);fillchar(f,sizeof(f),false);for i:=1 to n dobeginfor j:=1 to m dobeginread(a[i,j]);if a[i,j]=0 then begin a[i,j]:=maxlongint; f[i,j]:=true; end;k[i,j]:=maxlongint div 2;end;readln;end;for i:=1 to m doif f[1,i]=false thenbegink[1,i]:=k[1,i-1]+a[1,i];d[1,i]:=1;end;for i:=2 to n doif f[i,1]=false thenbegink[i,1]:=k[i-1,1]+a[i,1];d[i,1]:=2;endelse break;for i:=2 to n dofor j:=2 to m doif f[i,j]=false thenif ((k[i-1,j]+a[i,j])<(k[i,j-1]+a[i,j]))and(f[i-1,j]=false) thenbegind[i,j]:=2;k[i,j]:=k[i-1,j]+a[i,j];endelseif f[i,j-1]=false thenbegind[i,j]:=1;k[i,j]:=k[i,j-1]+a[i,j];end;dg(n,m);writeln;writeln(k[n,m]-a[n,m]);
end.

轉(zhuǎn)載于:https://www.cnblogs.com/Comfortable/p/8412392.html

總結(jié)

以上是生活随笔為你收集整理的SSL 1460——最小代价问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。