Есть прямоугольная таблица размером N
строк на M
столбиков. В каждой клетке записано целое число. По ней нужно пройти сверху вниз, начиная из любой клетки верхней строки, дальше двигаясь вниз ходами коня и закончить маршрут в какой-нибудь клетке нижней строки. То есть, из клетки (i, j) можно перейти в (i+1, j–2), или в (i+2, j–1), или в (i+2, j + 1), или в (i+1, j + 2), исключая варианты, выходящие за пределы доски.
Напишите программу, которая будет находить максимально возможную сумму значений пройденных клеток среди всех допустимых путей ходами коня, проходящих хотя бы по одному разу через каждый из столбиков.
В первой строке записаны N
и M
- количество строчек и количество столбиков (1 ≤ N ≤ 42
, 1 ≤ M ≤ 17
); дальше в каждой из следующих N
строк записано ровно M
разделённых пробелами целых чисел (каждое не превышает по модулю 10^6
) - значения клеток таблицы.
Вывести либо единственное целое число (найденную максимальную среди сумм по маршрутам указанного вида), либо строку "impossible" (без кавычек, маленькими латинскими буквами). Строка "impossible" должна выводиться только в том случае, когда не существует ни одного маршрута ходами коня, проходящего через все столбики хотя бы по одному разу.
Для поля 4×3 есть ровно четыре способа спуститься ходами коня, посетив каждый столбик:
Первый - a[1][1]->a[2][3]->a[4][2]
Второй - a[1][2]->a[3][1]->a[4][3]
Третий - a[1][2]->a[3][3]->a[4][1]
Четвертый - a[1][3]->a[2][1]->a[4][2]
Максимальная возможная сумма 25 = 15 + 4 + 6 достигается на третьем из них.
Для поля 3×3 таких способов вообще нет.