Найти путь из одной клетки в другую - PascalABC.NET

Узнай цену своей работы

Формулировка задачи:

В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку (N, N), чтобы сумма цифр в клетках, через которые он пролегает, была минимальной; из любой клетки ходить можно только вниз или вправо. Входные данные В первой строке находится число N (2 ≤ N ≤ 250). В следующих N строках содержатся по N цифр без пробелов. Выходные данные Выводятся N строк по N символов. Символ решётка показывает, что маршрут проходит через эту клетку, а точка - что не проходит. Если путей с минимальной суммой цифр несколько, вывести любой.
Пытался, но не знаю опять же как использовать массив правильно в этом коде. Прошу помогите) Если вы есть другой способ, то напишите пожалуйста.

Решение задачи: «Найти путь из одной клетки в другую»

textual
Листинг программы
/// Чтобы удобно было смотреть на выводимый массив
procedure WriteArray(A : array [,] of Integer);
begin
  var D := A[0, 0];
  for var Row := 0 to A.GetLength(0) - 1 do
    for var Col := 0 to A.GetLength(1) - 1 do
      D := Max(D, A[Row, Col]);
  D := D.ToString.Length + 1;
  for var Row := 0 to A.GetLength(0) - 1 do
    begin
      for var Col := 0 to A.GetLength(1) - 1 do
        Write(A[Row, Col]:D);
      WriteLn;
    end;
end;
 
begin
  // Заполнение массива случайными числами
  Randomize;
  var N := ReadLnInteger('N =');
  var A : array [,] of Integer;
  SetLength(A, N, N);
  for var Row := 0 to Pred(N) do
    for var Col := 0 to Pred(N) do
      A[Row, Col] := Random(0, 9);
  WriteLn('Массив заполнен случайными числами:');
  WriteArray(A);
  
  // Нахождение минимальных сумм
  var S : array [,] of Integer;
  SetLength(S, N, N);
  S[0, 0] := A[0, 0];
  // >-> Первая колонка
  for var Row := 1 to N-1 do S[Row, 0] := S[Pred(Row), 0] + A[Row, 0];
  // >-> Первый ряд
  for var Col := 1 to N-1 do S[0, Col] := S[0, Pred(Col)] + A[0, Col];
  // >-> Правее и ниже первых колонок и ряда
  for var Row := 1 to N-1 do
    for var Col := 1 to N-1 do
      S[Row, Col] := min(S[Row-1, Col], S[Row, Col-1]) + A[Row, Col];
  WriteLn('Массив с заполнением минимальных сумм по маршруту:');
  WriteArray(S);
  
  // Массив для маршрута
  var Path : array [,] of Char;
  SetLength(Path, N, N);
  for var Row := 0 to N-1 do
    for var Col := 0 to N-1 do
      Path[Row, Col] := '.';
 
  // Заполнение минимального маршрута с конца
  var tRow := N-1; var tCol := N-1;
  repeat
    Path[tRow, tCol] := '#';
    if S[tRow-1, tCol] < S[tRow, tCol-1] then
      tRow -= 1
    else
      tCol -= 1;
  until (tRow = 0) or (tCol = 0); // Достигли первого ряда или столбца
 
  while tRow > 0 do // Просто движемся вверх
    begin
      Path[tRow, tCol] := '#';
      tRow -= 1;
    end;
 
  while tCol > 0 do // Просто движемся влево
    begin
      Path[tRow, tCol] := '#';
      tCol -= 1;
    end;
  Path[tRow, tCol] := '#';
  
  // Результат
  WriteLn('Решение:');
  for var Row := 0 to N-1 do
    begin
      for var Col := 0 to N-1 do
        Write(Path[Row, Col]);
      WriteLn;
    end;
end.

Объяснение кода листинга программы

  1. Создание процедуры для вывода массива на экран.
  2. Заполнение массива случайными числами.
  3. Нахождение минимальных сумм.
  4. Создание массива для маршрута.
  5. Заполнение минимального маршрута с конца.
  6. Проверка наличия пути от последней клетки до первой.
  7. В случае наличия пути, его построение.
  8. Вывод решения на экран.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

7   голосов , оценка 4.143 из 5
Похожие ответы