題意

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

分析

k[i,j]:=a[i,j]+max(k[i,j-1]+a[i,j],k[i-1,j]+a[i,j]);

結(jié)果=k[n,m]-a[n,m]

var
n,m,i,j:longint;
d,k,a:array[0..100,0..100]of longint;
f:array[0..100,0..100]of boolean;
procedure dg(x,y:longint);
begin
? ? if (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;
begin
? ? readln(n,m);
? ? fillchar(f,sizeof(f),false);
? ? for i:=1 to n do
? ? begin
? ? ? ? for j:=1 to m do
? ? ? ? begin
? ? ? ? ? ? read(a[i,j]);
? ? ? ? ? ? if a[i,j]=0 then f[i,j]:=true;
? ? ? ? ? ? k[i,j]:=maxlongint div 2;
? ? ? ? end;
? ? ? ? readln;
? ? end;
? ? for i:=1 to m do
? ? if f[1,i]=false then
? ? begin
? ? ? ? k[1,i]:=k[1,i-1]+a[1,i];
? ? ? ? d[1,i]:=1;
? ? end else break;
? ? for i:=2 to n do
? ? if f[i,1]=false then
? ? begin
? ? ? ? k[i,1]:=k[i-1,1]+a[i,1];
? ? ? ? d[i,1]:=2;
? ? end else break;


? ? for i:=2 to n do
? ? begin
? ? ? ? for j:=2 to m do
? ? ? ? begin
? ? ? ? ? ? if (f[i,j]=false) then
? ? ? ? ? ? if ((k[i-1,j]+a[i,j])<(k[i,j-1]+a[i,j]))and(f[i-1,j]=false) then
? ? ? ? ? ? begin
? ? ? ? ? ? ? ? k[i,j]:=k[i-1,j]+a[i,j];
? ? ? ? ? ? ? ? d[i,j]:=2;
? ? ? ? ? ? end else
? ? ? ? ? ? if (f[i,j-1]=false) then
? ? ? ? ? ? begin
? ? ? ? ? ? ? ? k[i,j]:=k[i,j-1]+a[i,j];
? ? ? ? ? ? ? ? d[i,j]:=1;
? ? ? ? ? ? end;
? ? ? ? end;
? ? end;
? ? dg(n,m);
? ? writeln;
? ? write(k[n,m]-a[n,m]);


end.

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/9500170.html

總結(jié)

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

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