Distància de cavall màxima P12327


Statement
 

pdf   zip

html

Considereu un tauler d’escacs f × c amb caselles lliures i prohibides. Donades dues caselles lliures c1 i c2, heu d’anar de c1 fins a c2 fent el mínim nombre de salts de cavall possibles, sense sortir del tauler ni passar mai per cap casella prohibida. Escolliu c1 i c2 per maximitzar el nombre de salts del camí òptim entre les dues.

Si no recordeu com es mouen els cavalls, mireu la figura: El cavall blanc es podria moure a qualsevol casella amb un cavall negre:

Entrada

L’entrada consisteix en diversos casos, cadascun amb les dimensions f i c, seguides del nombre de posicions prohibides p. A continuació vénen p posicions prohibides diferents x y, amb 1 ≤ x ≤ f, i 1 ≤ y ≤ c. Suposeu 0 ≤ p < f · c ≤ 100.

largeboard, showmover=false, label=false, maxfield=e5, setpieces=na2,na4,ne2,ne4,Nc3,nb1,nd1,nb5,nd5

Sortida

Per a cada cas, escriviu la màxima distància entre dues caselles lliures qualssevol. S’ha de poder arribar d’una casella a l’altra. Si no es pot fer cap salt, escriviu 0.

Observació

Podeu obtenir 60 punts resolent casos amb f · c ≤ 25.

Public test cases

  • Input

    3 3
0
3 3
1 1 2
1 1
0
2 5
4 1 5 1 4 1 3 2 4

    Output

    4
6
0
1
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++ Python
    User solutions
    C++ Python