Найти путь из одной клетки в другую - PascalABC.NET
Формулировка задачи:
В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку (N, N), чтобы сумма цифр в клетках, через которые он пролегает, была минимальной; из любой клетки ходить можно только вниз или вправо.
Входные данные
В первой строке находится число N (2 ≤ N ≤ 250). В следующих N строках содержатся по N цифр без пробелов.
Выходные данные
Выводятся N строк по N символов. Символ решётка показывает, что маршрут проходит через эту клетку, а точка - что не проходит. Если путей с минимальной суммой цифр несколько, вывести любой.
Пытался, но не знаю опять же как использовать массив правильно в этом коде. Прошу помогите)
Если вы есть другой способ, то напишите пожалуйста.
Листинг программы
- program a8;
- const
- var
- x,n,c,c1,i,s,r:integer;
- begin
- readln (n);
- c:=2;
- c1:=250;
- s:=1;
- while n<c do
- begin
- writeln('Введите значение больше 2');
- readln(n);
- end;
- while n>c1 do
- begin
- writeln('Введите значение меньше 250');
- readln(n);
- end;
- p:=sqr(n);
- writeln('Введите: ',n,' символа(ов) в каждую строку');
- for i:=1 to n do s:=s*10;
- for i:=1 to n do begin
- readln(x);
- if x>s then
- writeln ('вы ввели количество цифр больше ', n, 'перезапустите программу.')
- else
- for r:=1 to n do begin
- end;
- end;
- end.
Решение задачи: «Найти путь из одной клетки в другую»
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.
Объяснение кода листинга программы
- Создание процедуры для вывода массива на экран.
- Заполнение массива случайными числами.
- Нахождение минимальных сумм.
- Создание массива для маршрута.
- Заполнение минимального маршрута с конца.
- Проверка наличия пути от последней клетки до первой.
- В случае наличия пути, его построение.
- Вывод решения на экран.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д