06/04/2025 12:00:30

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

35. Маршрут

Ограничения: время – 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$ символов. Символ решётка показывает, что маршрут проходит через эту клетку, а минус – что не проходит. Если путей с минимальной суммой цифр несколько, вывести любой.

Пример ввода

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

#--
###
--#

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

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)
19/03/2025	ЦОП1: динамическое программирование (проводит BOGAT) (E)