Модуль: 11.1G Динамическое программироварие. Часть 7. Интересные задачи


Задача

5 /5


Маршрут(2)


Задача

Дана матрица N*N, заполненная положительными числами. Путь по матрице начинается в левом верхнем углу. За один ход можно пройти в соседнюю по вертикали или горизонтали клетку (если она существует). Нельзя ходить по диагонали, нельзя оставаться на месте. Требуется найти максимальную сумму чисел, стоящих в клетках по пути длиной K (клетку можно посещать несколько раз).

Входные данные
В первой строке находятся разделенные пробелом числа N и K. Затем идут N строк по N чисел в каждой. 2 <= N <= 100, элементы матрицы имеют значения от 1 до 9999, 1 <= K <= 2000, все числа целые.

Выходные данные
Вывести одно число - максимальную сумму.
Примеры
Входные данныеВыходные данные
1 5 7
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 100
7

time 3000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w641
Комментарий учителя