printЗанятие 9

printB. Маршрут

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

В таблице из `N` строк и `N` столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку `(N,\ N)`, чтобы сумма цифр в клетках, через которые он пролегает, была минимальной; из любой клетки ходить можно только вниз или вправо.
Ввод
В первой строке находится число `N\ (2\ ≤\ N\ ≤\ 250)`. В следующих `N` строках содержатся по `N` цифр без пробелов.
Вывод
Выводятся `N` строк по `N` символов. Символ решётка показывает, что маршрут проходит через эту клетку, а минус – что не проходит. Если путей с минимальной суммой цифр несколько, вывести любой.

Пример ввода

3
943
216
091

Пример вывода

#--
###
--#
Источник: Сипин, Меньшиков
loading