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

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

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

В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку (N, N), чтобы сумма цифр в клетках, через которые он пролегает, была минимальной; из любой клетки ходить можно только вниз или вправо. Входные данные В первой строке находится число N (2 ≤ N ≤ 250). В следующих N строках содержатся по N цифр без пробелов. Выходные данные Выводятся N строк по N символов. Символ решётка показывает, что маршрут проходит через эту клетку, а точка - что не проходит. Если путей с минимальной суммой цифр несколько, вывести любой.
Листинг программы
  1. program a8;
  2. const
  3. var
  4. x,n,c,c1,i,s,r:integer;
  5. begin
  6. readln (n);
  7. c:=2;
  8. c1:=250;
  9. s:=1;
  10. while n<c do
  11. begin
  12. writeln('Введите значение больше 2');
  13. readln(n);
  14. end;
  15. while n>c1 do
  16. begin
  17. writeln('Введите значение меньше 250');
  18. readln(n);
  19. end;
  20. p:=sqr(n);
  21. writeln('Введите: ',n,' символа(ов) в каждую строку');
  22. for i:=1 to n do s:=s*10;
  23. for i:=1 to n do begin
  24. readln(x);
  25. if x>s then
  26. writeln ('вы ввели количество цифр больше ', n, 'перезапустите программу.')
  27. else
  28. for r:=1 to n do begin
  29. end;
  30. end;
  31. end.
Пытался, но не знаю опять же как использовать массив правильно в этом коде. Прошу помогите) Если вы есть другой способ, то напишите пожалуйста.

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

textual
Листинг программы
  1. /// Чтобы удобно было смотреть на выводимый массив
  2. procedure WriteArray(A : array [,] of Integer);
  3. begin
  4.   var D := A[0, 0];
  5.   for var Row := 0 to A.GetLength(0) - 1 do
  6.     for var Col := 0 to A.GetLength(1) - 1 do
  7.       D := Max(D, A[Row, Col]);
  8.   D := D.ToString.Length + 1;
  9.   for var Row := 0 to A.GetLength(0) - 1 do
  10.     begin
  11.       for var Col := 0 to A.GetLength(1) - 1 do
  12.         Write(A[Row, Col]:D);
  13.       WriteLn;
  14.     end;
  15. end;
  16.  
  17. begin
  18.   // Заполнение массива случайными числами
  19.   Randomize;
  20.   var N := ReadLnInteger('N =');
  21.   var A : array [,] of Integer;
  22.   SetLength(A, N, N);
  23.   for var Row := 0 to Pred(N) do
  24.     for var Col := 0 to Pred(N) do
  25.       A[Row, Col] := Random(0, 9);
  26.   WriteLn('Массив заполнен случайными числами:');
  27.   WriteArray(A);
  28.  
  29.   // Нахождение минимальных сумм
  30.   var S : array [,] of Integer;
  31.   SetLength(S, N, N);
  32.   S[0, 0] := A[0, 0];
  33.   // >-> Первая колонка
  34.   for var Row := 1 to N-1 do S[Row, 0] := S[Pred(Row), 0] + A[Row, 0];
  35.   // >-> Первый ряд
  36.   for var Col := 1 to N-1 do S[0, Col] := S[0, Pred(Col)] + A[0, Col];
  37.   // >-> Правее и ниже первых колонок и ряда
  38.   for var Row := 1 to N-1 do
  39.     for var Col := 1 to N-1 do
  40.       S[Row, Col] := min(S[Row-1, Col], S[Row, Col-1]) + A[Row, Col];
  41.   WriteLn('Массив с заполнением минимальных сумм по маршруту:');
  42.   WriteArray(S);
  43.  
  44.   // Массив для маршрута
  45.   var Path : array [,] of Char;
  46.   SetLength(Path, N, N);
  47.   for var Row := 0 to N-1 do
  48.     for var Col := 0 to N-1 do
  49.       Path[Row, Col] := '.';
  50.  
  51.   // Заполнение минимального маршрута с конца
  52.   var tRow := N-1; var tCol := N-1;
  53.   repeat
  54.     Path[tRow, tCol] := '#';
  55.     if S[tRow-1, tCol] < S[tRow, tCol-1] then
  56.       tRow -= 1
  57.     else
  58.       tCol -= 1;
  59.   until (tRow = 0) or (tCol = 0); // Достигли первого ряда или столбца
  60.  
  61.   while tRow > 0 do // Просто движемся вверх
  62.     begin
  63.       Path[tRow, tCol] := '#';
  64.       tRow -= 1;
  65.     end;
  66.  
  67.   while tCol > 0 do // Просто движемся влево
  68.     begin
  69.       Path[tRow, tCol] := '#';
  70.       tCol -= 1;
  71.     end;
  72.   Path[tRow, tCol] := '#';
  73.  
  74.   // Результат
  75.   WriteLn('Решение:');
  76.   for var Row := 0 to N-1 do
  77.     begin
  78.       for var Col := 0 to N-1 do
  79.         Write(Path[Row, Col]);
  80.       WriteLn;
  81.     end;
  82. end.

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

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

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


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

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

7   голосов , оценка 4.143 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы