MaxSum (atı hərəkəti ilə bütün sütunları ziyarət etmək)
Є N x M ölçüsündə bir düzbucaqlı cədvəl verilmişdir. Hər bir hüceyrədə bir tam ədəd yazılıb. Sizdən tələb olunan, cədvəlin yuxarı sətrindən başlayaraq, at gedişləri ilə hərəkət edərək və marşrutu aşağı sətrin hər hansı bir hüceyrəsində bitirərək, mümkün olan ən böyük cəmi tapmaqdır. Hərəkət zamanı yuxarıdan aşağıya doğru hərəkət etməli və hər sütundan ən azı bir dəfə keçməlisiniz. At gedişləri ilə (i, j) hüceyrəsindən (i+1, j-2), (i+2, j-1), (i+2, j+1) və ya (i+1, j+2) hüceyrələrinə keçmək mümkündür, lakin lövhənin hüdudlarından kənara çıxmaq olmaz.
Proqram yazın ki, bu şərtlərə uyğun olaraq keçilən hüceyrələrin dəyərlərinin maksimum cəmini tapsın.
Giriş verilənləri
Birinci sətirdə N və M - sətirlərin və sütunların sayı (1 ≤ N ≤ 42, 1 ≤ M ≤ 17); növbəti N sətirdə isə M boşluqla ayrılmış tam ədədlər (hər biri modulu 10^6-dan çox olmayan) - cədvəl hüceyrələrinin dəyərləri verilir.
Çıxış verilənləri
Ya bir tam ədəd (göstərilən tipdəki marşrutlar üzrə tapılan maksimum cəmi), ya da "impossible" (tırnaqsız, kiçik latın hərfləri ilə) sətirini çıxarın. "impossible" sətiri yalnız at gedişləri ilə hər sütundan ən azı bir dəfə keçən heç bir marşrut olmadıqda çıxarılmalıdır.
Qeyd: 4×3 sahəsi üçün hər sütundan keçərək at gedişləri ilə enməyin dörd yolu var:
Maksimum mümkün cəm 25 = 15 + 4 + 6 üçüncü yolda əldə edilir.
3×3 sahəsi üçün belə yollar ümumiyyətlə yoxdur.