В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1;1) в клетку (N;N), чтобы сумма цмфр в клетках, через которые он пролегает, была минимальной; из любой клетки ходить можно только вниз или вправо.
2<=N<=250;
Ввод: первая строка - N, в следующих содержатся N цифр без пробелов.
Вывод: Выводится N строк по N символов. Символ "решетка" показывает, что маршрут проходит через эту клетку, а минус что не проходит. Если путей с минимальной суммой цифр несколько, вывести любой. Пример.
Ввод
3
943
216
091
Вывод
#--
###
--#
Прошу пока не писать решение, а направить меня в нужном направлении по поводу решения этой задачи. Т.е. посоветовать что надо делать, примерный алгоритм действий.
.