Distància de cavall màxima P12327

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

0.55 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 \le x \le f$, i $1 \le y \le c$. Suposeu $0 \le p < f \cdot c \le 100$.

0.45

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 \cdot c \le 25$.