Задача №619. Маршрут. Условие задачи из дистанционного курса подготовки по информатике.

Задача №619. Маршрут

Ссылка на сайт:

http://informatics.mccme.ru/mod/statements/view.php?id=634#1

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.

В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку (N, N), чтобы сумма цифр в клетках, через которые он пролегает, была минимальной; из любой клетки ходить можно только вниз или вправо.

Входные данные

В первой строке находится число N. В следующих N строках содержатся по N цифр без пробелов. 2  N 

Выходные данные

Выводятся N строк по N символов. Символ решётка показывает, что маршрут проходит через эту клетку, а минус - что не проходит. Если путей с минимальной суммой цифр несколько, вывести любой.

Примеры

входные данные

2

00

00

выходные данные

#-

##

Задача решена на 100%.

Const FIXMAX=250;

Var a,b,c,res:array[1..FIXMAX,1..FIXMAX]of integer;

s:string;

i,n,j,x,y,code:integer;

t1,t2:text;

Begin

assign(t1,'input.txt');reset(t1);

assign(t2,'output.txt');rewrite(t2);

readln(t1,n);

for x:=1 to n do begin

read(t1,s);

for y:=1 to n do begin

val(s[y],a[x,y],code);

b[x,y]:=2500;

end;

readln(t1);

end;

close(t1);

res[n,n]:=1;

res[1,1]:=1;

b[1,1]:=a[1,1];

for x:=1 to n do begin

i:=0;

j:=x;

While ij do begin

inc(i);

if (j=n)and(j=i)then break;

if b[i+1,j]=(a[i+1,j]+b[i,j])then begin b[i+1,j]:=a[i+1,j]+b[i,j];

c[i+1,j]:=0;

end;

if b[j,i+1]=(a[j,i+1]+b[j,i])then begin b[j,i+1]:=a[j,i+1]+b[j,i];

c[j,i+1]:=1;

end;

if (b[i,j+1]=(a[i,j+1]+b[i,j]))and(jn)then begin b[i,j+1]:=a[i,j+1]+b[i,j];

c[i,j+1]:=1;

end;

if (b[j+1,i]=(a[j+1,i]+b[j,i]))and(jn)then begin b[j+1,i]:=a[j+1,i]+b[j,i];

c[j+1,i]:=0;

end;

end;

end;

for x:=2*n-1 downto 2 do

if c[i,j]=0 then begin dec(i);

res[i,j]:=1;

end

else begin dec(j);

res[i,j]:=1;

end;

for i:=1 to n do begin

for j:=1 to n do

if res[i,j]=0 then write(t2,'-')

else write(t2,'#');

writeln(t2);

end;

close(t2);

End.