6. Динамическое программирование

Разбор задачи 35. Маршрут

var 
  n,i,j,c:integer;
  m:array[1..250]of string; { матрица цифр }
  t:array[1..250,1..250] of integer; { таблица для 
     динамического программирования - лучшая сумма }
begin
  readln(n);
  for i:=1 to n do
    readln(m[i]);
  { прямая трассировка }
  for i:=1 to n do
    for j:=1 to n do
    begin
      c:=ord(m[i][j])-ord('0'); { цифра в клетке (i,j) }
      if (i=1) and (j=1) then
        t[i,j]:=c
      else if (i>1) and ((j=1) or (t[i-1,j]<t[i,j-1])) then 
        t[i,j]:=t[i-1,j]+c
      else 
        t[i,j]:=t[i,j-1]+c;
    end;
  { обратная трассировка }
  i:=n;
  j:=n;
  while (i>1) or (j>1) do
  begin
    m[i][j]:='#';
    { из двух направлений выбираем с меньшей суммой или 
      единственно возможное }
    if (i>1) and ((j=1) or (t[i-1,j]<t[i,j-1])) then 
      dec(i)
    else
      dec(j);
  end;
  m[1][1]:='#';
  { замена остальных цифр на '-' и вывод }
  for i:=1 to n do
  begin
    for j:=1 to n do
      if m[i][j]<>'#' then m[i][j]:='-';
    writeln(m[i]);
  end;
end.