Cavalls voraços P39621


Statement
 

pdf   zip

thehtml

Considereu un tauler n × m on a cada casella hi ha un cert nombre de monedes. Es vol cobrir la màxima quantitat de monedes possible amb cavalls dels escacs. L’única restricció és que els cavalls no es poden amenaçar entre si.

Entrada

L’entrada consisteix en diversos casos, cadascun amb n i m, seguides d’n files amb m naturals cadascuna, que indiquen el nombre de monedes que hi ha a cada casella del tauler. Suposeu n ≥ 2, m ≥ 2, n · m ≤ 30, i que cada casella té entre 0 i 106 monedes.

Sortida

Per a cada cas, escriviu el màxim nombre de monedes que es poden cobrir amb cavalls que no s’amenacin entre si.

Observació

La solució esperada per a aquest problema és un backtracking senzill.

Public test cases
  • Input

    2 3
    38 10 41
    50 15 50
    
    3 4
    11 20 31 40
    50 61 70 81
    91 90 71 60
    
    2 6
    1 2 1000000 1000000 5 6
    3 4 1000000 1000000 7 8
    

    Output

    125
    346
    4000000
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++ Python
    User solutions
    C++ Python