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