Cavalls voraços P39621
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.
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
- Author
- Salvador Roura
- Language
- Catalan
- Official solutions
- C++ Python
- User solutions
- C++