Отметить цветом(указать) путь из A[1,1] в A[8,8],такой,что сумма "пройденных" элементов минимальна

[XanderXage]

Задание:Матрица 8*8 случайно заполнена числами 0-5.Отметить цветом(указать) путь из A[1,1] в A[8,8],такой,что сумма "пройденных" элементов минимальна.За один шаг можно ходить вниз или вправо.
Не знаю даже с чего подступиться.С заданием матрицы рандом проблем нет,а вот дальше..дальше лес,никак не сориентируюсь даже как начать основной этот "ПУТЬ".Может кто поможет и побудет путепрокладчиком?Самому интересно,как это составить...

[val_nnm]

Простейший вариант (как мне кажется, хотя возможно существуют и более прсые варианты): Составить матрицу минимальных путей.
Создаёте матрицу B размером 8x8 инициализируем B[1,1] = A[1,1]
Дальше заполняем первый столбец
B[1,2] = B[1,1] + A[1,2]
B[1,3] = B[1,2] + A[1,3]
...
B[1,8] = B[1,7] + A[1,8]

Дальше цикл по всем столбцам. (i = 2..8)
B[i,1] = B[i-1,1]+A[i,1]
а все остальные
B[i,2] = min(B[i,1],B[i-1,2])+A[i,2]
B[i,3] = min(B[i,2],B[i-1,3])+A[i,3]
B[i,4] = min(B[i,3],B[i-1,4])+A[i,4]
...
B[i,8] = min(B[i,7],B[i-1,8])+A[i,8]

после этого цикла в элементе B[8,8] будет находиться минимальный путь.
Дальше чтобы получить список элементов через которые прошел этот путь. То нужно пройти по матрице B в обратном порядке из B[8,8] в B[1,1] двигаясь вверх в влево (выбирая путь по минимальным значениям B)
т.е. если мы находимся в точке B[i,j] то
если B[i-1,j]<B[i,j-1] то идем влево (i = i-1 ) иначе идём вверх (j = j-1)
(только не забудьте дополнительно проверить i и j на равенство 1 чтобы не выйти за границы массива)

Ни или можно формировать изначально матрицу начиная с B[8,8] к B[1,1] а путь искать от B[1,1] к B[8,8]



Решил реализовать для истории (может кому нибудь понадобиться)

Const m = 8;
      n = 8;
Type Arr = array[1..m,1..n] of integer;

var i,j:integer;
    pi,pj:integer;
    A:Arr;
    B:Arr;
Begin
  Randomize;
  for i := 1 to m do
   for j := 1 to n do
     A[i,j] := Random(6);
  B[m,n] := A[m,n];

  for i := m-1 downto 1 do
    B[i,n] := B[i+1,n]+A[i,n];

  for j := n-1 downto 1 do Begin
    B[m,j] := B[m,j+1] + A[m,j];
    for i := m-1 downto 1 do Begin
      if (B[i,j+1]<B[i+1,j]) then
        B[i,j] := B[i,j+1]+A[i,j]
      else
        B[i,j] := B[i+1,j]+A[i,j]
    end;
  end;

  pi := 1;
  pj := 1;
  for i := 1 to m do Begin
    for j := 1 to n do
      if (pi = i) and (pj = j) then Begin
        write('(',A[i,j]:1,')');
        if (pi=m) then
          pj := pj + 1
        else
          if (pj=n) then
            pi := pi+1
          else Begin
            if (B[pi+1,pj]<B[pi,pj+1]) then
              pi := pi+1
            else
              pj := pj+1;
          end;
      end else
        write(' ',A[i,j]:1,' ');
    writeln;
  end;
end.

[XanderXage]

Спасибо!только вот как скобочки заменить на другой цвет?а то выделение в скобочках это же немного не то.

[val_nnm]

Ну подумайте сами немного. За вас уже и так всю программу написали. Вам осталось вставить 3 и изменить 1 или 2 строчки.
Используйте модуль crt и изменяйте цвет ("textcolor(Red);" и "textcolor(LightGray);")

[Serge_Bliznykov]

Сообщение от val_nnm

Решил реализовать для истории (может кому нибудь понадобиться)

ну да, всё так.

Ну, просто маленькое замечание.
Это классическая задача на динамическое программирование. На форуме алгоритм решения был "разжёван" неоднократно:
ТЫЦ