Задача №619. Маршрут
Динамическое программирование
В таблице из \(N\) строк и \(N\) столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку (\(N\), \(N\)), чтобы сумма цифр в клетках, через которые он пролегает, была минимальной; из любой клетки ходить можно только вниз или вправо.
Входные данные
В первой строке находится число \(N\). В следующих \(N\) строках содержатся по \(N\) цифр без пробелов. 2 <= \(N\) <= 250.
Выходные данные
Выводятся \(N\) строк по \(N\) символов. Символ решётка показывает, что маршрут проходит через эту клетку, а минус - что не проходит. Если путей с минимальной суммой цифр несколько, вывести любой.
Примеры
Входные данные
2 00 00
Выходные данные
#- ##
Входные данные
2 00 90
Выходные данные
## -#
Сдать: для сдачи задач необходимо войти в систему