eolymp
bolt
Try our new interface for solving problems
Məsələlər

MaxSum (посетить все столбики ходами коня)

MaxSum (посетить все столбики ходами коня)

Zaman məhdudiyyəti 4 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Есть прямоугольная таблица размером N строк на M столбиков. В каждой клетке записано целое число. По ней нужно пройти сверху вниз, начиная из любой клетки верхней строки, дальше двигаясь вниз ходами коня и закончить маршрут в какой-нибудь клетке нижней строки. То есть, из клетки (i, j) можно перейти в (i+1, j–2), или в (i+2, j–1), или в (i+2, j + 1), или в (i+1, j + 2), исключая варианты, выходящие за пределы доски.

Напишите программу, которая будет находить максимально возможную сумму значений пройденных клеток среди всех допустимых путей ходами коня, проходящих хотя бы по одному разу через каждый из столбиков.

Giriş verilənləri

В первой строке записаны N и M - количество строчек и количество столбиков (1N42, 1M17); дальше в каждой из следующих N строк записано ровно M разделённых пробелами целых чисел (каждое не превышает по модулю 10^6) - значения клеток таблицы.

Çıxış verilənləri

Вывести либо единственное целое число (найденную максимальную среди сумм по маршрутам указанного вида), либо строку "impossible" (без кавычек, маленькими латинскими буквами). Строка "impossible" должна выводиться только в том случае, когда не существует ни одного маршрута ходами коня, проходящего через все столбики хотя бы по одному разу.

Примечание: Для поля 4×3 есть ровно четыре способа спуститься ходами коня, посетив каждый столбик:

Максимальная возможная сумма 25 = 15 + 4 + 6 достигается на третьем из них.

Для поля 3×3 таких способов вообще нет.

Nümunə

Giriş verilənləri #1
4 3
1 15 2
9 7 5
9 2 4
6 9 -1
Çıxış verilənləri #1
25
Giriş verilənləri #2
3 3
1 15 2
9 7 5
9 2 4
Çıxış verilənləri #2
impossible
Müəllif Илья Порублёв
Mənbə Летняя школа Севастополь 2013, Волна 1, День 2