НачалоПодразделы
Другие разделы
Дата и время
20/12/2024 13:48:12
Занятие 9
B. Маршрут
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 03/07/2006 | Лето 2006 дорешивание ( 3B) |
| 07/07/2006 | Лето 2006 - 3 (B) |
| 07/11/2007 | Занятие 9 (B) |
| 25/10/2008 | Занятие 6 (B) |
| 09/12/2010 | Сборы: Общий итог (6A) |
| 13/01/2011 | Сборы 6: Практика (A) |
| 23/02/2023 | Базовый уровень: динамическое программирование 1 (проводит BOGAT) (E) |
| 12/07/2023 | Лето 2023-8 простые (A) |
| 27/02/2024 | Динамическое программирование 1 (проводит BOGAT) (E) |
| 10/07/2024 | Лето 2024-8 простые (A) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
В таблице из `N` строк и `N` столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку `(N,\ N)`, чтобы сумма цифр в клетках, через которые он пролегает, была минимальной; из любой клетки ходить можно только вниз или вправо.
Ввод
В первой строке находится число `N\ (2\ ≤\ N\ ≤\ 250)`. В следующих `N` строках содержатся по `N` цифр без пробелов.
Вывод
Выводятся `N` строк по `N` символов. Символ решётка показывает, что маршрут проходит через эту клетку, а минус – что не проходит. Если путей с минимальной суммой цифр несколько, вывести любой.
Пример ввода
3 943 216 091
Пример вывода
#-- ### --#
