Cho một ma trận vuông kích thước N*M chỉ chứa các số nguyên không âm. Ban đầu đặt một robot ở ô (1,1), yêu cầu tìm đường đi đến ô (N, M) sao cho chi phí thu được là nhỏ nhất. Biết rằng, tại ô (i, j) chỉ được đi sang ô (i+1, j) hoặc (i, j+1). Chi phí của đường đi được xác định bằng số chữ số 0 tận cùng của tích các số trên đường đi.
Input:
– Dòng đầu tiên chứa số nguyên N, M (N, M ≤ 1000) là kích thước của ma trận
– N dòng tiếp theo, mỗi dòng chứa M số nguyên không âm và không vượt quá 109
Output: Một số nguyên duy nhất là chi phí của đường đi nhỏ nhất tìm được.
Ví dụ:
Input:
4 3
1 2 3
4 5 6
7 8 9
10 11 12
Output:
0
Giải thích: các cách đi thu được chi phí là 0:
– 1 → 2 → 3 → 6 → 9 → 12, 1*2*3*6*9*12 = 3888
– 1 → 4 → 7 → 8 → 9 → 12, 1*4*7*8*9*12 = 24192
– 1 → 4 → 7 → 8 → 11 → 12, 1*4*7*8*11*12 = 29568
Cho một ma trận vuông kích thước N*M chỉ chứa các số nguyên không âm. Ban đầu đặt một robot ở ô (1,1), yêu cầu tìm đường đi đến ô (N, M) sao cho chi p
By Nevaeh
uses crt;
var fi,fo:text;
n,m,i,j:integer;
a,b:array[-1..200,-1..200] of int64;
procedure taotep;
begin
assign(fi,’ChiPhi.inp’);
{$I-} reset(fi); {$I+}
if ioresult<>0 then
begin
rewrite(fi);
reset(fi);
end;
readln(fi,n,m);
for i:=1 to n do
begin
for j:=1 to m do read(fi,a[i,j]);
readln(fi);
end;
close(fi);
end;
function min(x,y:int64):int64;
begin
min:=x;
if y<x then min:=y;
end;
procedure taomang;
begin
b[1,1]:=a[1,1];
for i:=0 to n do b[i,0]:=999999999;
for j:=0 to m do b[0,j]:=999999999;
for j:=1 to m do
for i:=1 to n do
if (i<>1) or (j<>1) then
b[i,j]:=min(b[i-1,j],b[i,j-1])*a[i,j];
end;
procedure truyvet(i,j:integer);
begin
if (i>1) or (j>1) then
begin
if b[i-1,j]=min(b[i-1,j],b[i,j-1]) then truyvet(i-1,j)
else truyvet(i,j-1);
end;
write(a[i,j],’ ‘);
end;
BEGIN
clrscr;
taotep; taomang;
writeln(‘Chi phi toi thieu la:’,b[n,m]);
write(‘Duong di la:’);
truyvet(n,m);
readln
END.
Mình dùng cách quy hoạch động, dữ liệu vào ở tệp ‘ChiPhi.inp’, kết quả ghi ra màn hình.
Chúc bạn học tốt.
Cho mik xin ctlhn.