Program Problem6_4; 
Uses crt;
Type matrix = array [1..14, 1..14] of integer;
Var
 i, k, j, N, p: byte;
 A, B, U: matrix;
 C:array[1..26, 1..2] of integer;
{--- Функция нахождения максимального числа ----}
Function max(A1,A2:integer; var p:byte):integer;
Var integer;
Begin
  If A1>A2 Then d:= A1
   else
    Begin
      d:= A2;
      p:= 1;
    end;
  max:= d;
end;
{---- Процедура вывода матрицы на экран ----}
Procedure vivod(D: matrix);
Var i, j: byte;
Begin
  For i:=1 To N do
    Begin
      For j:=1 To N do Write('  ', D[i, j]);
      WriteLn;
     end;
end;
{--- Процедура вывода матрицы на экран с маршрутом следования ----}
Procedure vivodB(D: matrix);
Var 
    i, j: byte;
    h:string;
Begin
  For i:=1 To N do
    Begin
      For j:=1 To N do 
        Begin
           Case D[i, j] Of{Используем для большей наглядности}
            10..99: h:= ' ';
            100..999: h:= '';
            else  h:= '  ';
           end;{Вывод маршрута следования}
           If (u[i, j+1] = 1) And (j < N) Then Write(' ',D[i, j], h, '-')
                                          else Write(' ', D[i, j], h, ' ');
        end;
      WriteLn;
      For j:=1 To N do
        If (u[i+1, j] = 0) And (i < N) Then Write(' |   ')
                                       else Write('     ');
      WriteLn;
    end;
end;
{------ Код основной программы ------}
Begin
 clrscr;
 Repeat{Ввод размерности матрицы}
  Write('  Введите размерность матрицы (1..13): ');
  ReadLn(N);
 Until (N >= 1) And (N <= 13);
 randomize;
 For i:=1 To N do{Получение самой матрицы}
  For j:=1 To N do
   A[i, j]:= random(10);
 writeln;
 writeln(' Первоначальная матрица:');
 writeln;
 vivod(A); {Вызов процедуры вывода матрицы на экран}
 B[1,1]:= A[1,1];
 u[1,1]:= 0;
 For i:=2 To N do
  Begin{Заполнение первой строки и первого стобца матриц B и U}
   B[1,i]:= A[1,i] + B[1,i-1];
   u[1,i]:= 1;
   B[i,1]:= A[i,1] + B[i-1,1];
   u[i,1]:= 0;
  end;
 For i:=2 To N do{Заполнение матриц B и U}
  For j:=2 To N do
      Begin
       p:= 0;
       B[i,j]:= A[i,j] + max(B[i-1,j], B[i,j-1], p);
       u[i,j]:= p;
      end;
 WriteLn;
 WriteLn(' Максимальная сумма в каждой ячейке и путь ее получения: ');
 writeln;{Вывод значений  B и пути ее заполнения}
 vivodB(B); {Вызов процедуры}
 i:= N;
 k:= N;
 j:= 2*N-1;{Минимальное количество клеток маршрута}
 C[1,1]:= 1;{Первая ячейка маршрута}
 C[1,2]:= 1;
 While (i <> 1) Or (k <> 1) Do{Заполнение матрицы C - координаты движения}
  Begin
   C[j,1]:= i;
   C[j,2]:= k;
   If i = 1 Then Dec(k){Уменьшаем номер столбца}
          else
            If k = 1 Then Dec(i){Уменьшаем номер строки}
                   else
                    If max(b[i-1,k], b[i,k-1], p) = b[i,k-1] Then Dec(k)
                                                             else Dec(i);
   Dec(j);
  end;
 For i:=1 To N do{"Обнуляем" матрицу U}
  For j:=1 To N do
   u[i,j]:= 3;
 For i:=1 To 2*N-1 do
  If C[i,1] = C[i+1,1] Then u[C[i,1],C[i,2]+1]:= 1
                       else u[C[i,1]+1,C[i,2]]:= 0;
 WriteLn;
 writeln(' Путь следования в матрице:');
 WriteLn;{Вывод первоначальной матрицы А с путем следования в ней}
 vivodB(A);{Вызов процедуры}
 WriteLn;
 write(' Координаты маршрута: ');
 Write(C[1,1],',',C[1,2]);{Вывод маршрута следования в матрице А}
 For i:=2 To 2*N-1 do
  Write(' -> ',C[i,1],',',C[i,2]);
 ReadKey;
End.