Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Маршрут

(Время: 1 сек. Память: 16 Мб Сложность: 38%)

В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку (N, N), чтобы сумма цифр в клетках, через которые он пролегает, была минимальной; из любой клетки ходить можно только вниз или вправо.

Входные данные

В первой строке входного файла INPUT.TXT находится число N. В следующих N строках содержатся по N цифр без пробелов. (2 ≤ N ≤ 250)

Выходные данные

В выходной файл OUTPUT.TXT выведите N строк по N символов. Символ «#» (решетка) показывает, что маршрут проходит через эту клетку, а «-» (минус) - что не проходит. Если путей с минимальной суммой цифр несколько, можно вывести любой.

Пример

INPUT.TXTOUTPUT.TXT
13
943
216
091
#--
###
--#

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Олимпиадные задачи по программированию, 2006
 Тренировка 1
 Тренировка 2
 Тренировка 3
 Тренировка 4
 Тренировка 5
 Тренировка 6
 Тренировка 7
 Тренировка 8
 Тренировка 9
 Тренировка 10
 Тренировка 11
 Тренировка 12
 Тренировка 13
 Тренировка 14
 Тренировка 15
 A. Простые числа
 B. Перестановки
 C. Маршрут
 D. Пересечение отрезков
 E. Длинная сумма
 F. Спираль

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru