Найти путь из одной клетки в другую - 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.
Объяснение кода листинга программы
- Создание процедуры для вывода массива на экран.
- Заполнение массива случайными числами.
- Нахождение минимальных сумм.
- Создание массива для маршрута.
- Заполнение минимального маршрута с конца.
- Проверка наличия пути от последней клетки до первой.
- В случае наличия пути, его построение.
- Вывод решения на экран.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д