最小代價問題Time Limit:1000MS Memory Limit:65536KTotal Submit:207 Accepted:72Description設有一個n×m(小于100)的方格（如圖所示），在方格中去掉某些點，方格中的數字代表距離（為小于100的數，如果為0表示去掉的點），試找出一條從A(左上角)到B（右下角）的路徑，經過的距離和為最小（此時稱為最小代價），從A出發的方向只能向右，或者向下。 InputOutputSample Input4 4 4 10 7 03 2 2 90 7 0 411 6 12 1Sample Output(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)24
var
i,j,n,m:longint; a:array[1..1000,1..1000]of longint; f:array[1..1000,1..1000,1..2]of longint;function mix(a,b:longint):longint; begin if a<b then exit(a); exit(b); end;PRocedure dg(x,y:longint); begin if (x<1) or (y<1) then exit; if f[x,y,2]=1 then dg(x,y-1) else dg(x-1,y); if (x<>n) or (y<>m) then write('(',x,',',y,')->') else write('(',x,',',y,')'); end;begin read(n,m); for i:=1 to n do for j:=1 to m do read(a[i,j]); f[1,1,1]:=a[1,1]; for i:=2 to n do if (a[1,i]<>0)and(f[1,i-1,1]<>0) then begin f[1,i,1]:=f[1,i-1,1]+a[1,i]; f[1,i,2]:=1; end; for j:=2 to m do if (a[j,1]<>0)and(f[j-1,1,1]<>0) then begin f[j,1,1]:=f[j-1,1,1]+a[j,1]; f[j,1,2]:=2; end; for i:=2 to n do for j:=2 to m do if (a[i,j]<>0) then begin if (f[i-1,j,1]=0)and(f[i,j-1,1]<>0)then begin f[i,j,1]:=f[i,j-1,1]+a[i,j]; f[i,j,2]:=1; end; if (f[i,j-1,1]=0)and(f[i-1,j,1]<>0) then begin f[i,j,1]:=f[i-1,j,1]+a[i,j]; f[i,j,2]:=2; end; if (f[i-1,j,1]<>0)and(f[i,j-1,1]<>0) then begin f[i,j,1]:=mix(f[i-1,j,1],f[i,j-1,1])+a[i,j]; if mix(f[i-1,j,1],f[i,j-1,1])=f[i-1,j,1] then f[i,j,2]:=2 else f[i,j,2]:=1; end; end; dg(n,m); writeln; write(f[n,m,1]-a[n,m]);end.新聞熱點
疑難解答
