Distància de cavall màxima P12327


Statement
 

pdf   zip

thehtml

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 ≤ xf, i 1 ≤ yc. 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