HAF1 - Đua Xe

Tác giả: RR

Ngôn ngữ: Pascal

{$R-,Q-}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=1000;
var
  n,m:longint;
  f1,f2:text;
  left,right,a:array[1..MAXN,1..MAXN] of longint;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure inp;
var
  i,j:longint;
begin
  read(f1,n,m);
  for i:=1 to m do
  for j:=1 to n do
    read(f1,a[i,j]);
end;
procedure ans;
var
  luu,j:longint;
begin
  luu:=maxlongint;
  for j:=1 to n do
    luu:=min(min(left[m,j],right[m,j]),luu);
  writeln(f2,luu);
end;
procedure solve;
var
  i,j:longint;
begin
  for j:=1 to n do
    begin
      left[1,j]:=a[1,j];
      right[1,j]:=a[1,j];
    end;
  for i:=2 to m do
    begin
      for j:=1 to n do
        begin
          left[i,j]:=min(left[i-1,j],right[i-1,j])+a[i,j];
          right[i,j]:=left[i,j];
        end;
      for j:=2 to n do
        right[i,j]:=min(right[i,j],right[i,j-1]+a[i,j]);
      for j:=n-1 downto 1 do
        left[i,j]:=min(left[i,j],left[i,j+1]+a[i,j]);
    end;
end;
begin
  openF;
  inp;
  solve;
  ans;
  closeF;
end.

Download