Cartero
Gustavo ha obtenido un trabajo de cartero en un pequeño pueblo en las montañas. El pueblo puede ser representado por una matriz de \(N×N\) campos. Cada campo contiene exclusivamente una de las siguientes cosas: una casa denotada \(‘K’\), la oficina de correo denotada por \(‘P’\), o pasto denotado por \(‘.’\). Adicionalmente, a cada campo se le asigna una altitud.
Cada mañana, Gustavo entrega la correspondencia a todas las casas en el pueblo. El comienza en el campo denotado por \(‘P’\), el cual representa la oficina de correos del pueblo. A Gustavo le está permitido moverse horizontalmente, verticalmente y diagonalmente, solamente a los cuadros adyacentes. Una vez que el entrega el último paquete, el tiene que retornar a la oficina de correo.
Gustavo no tiene idea de cuan agotador será su trabajo. La diferencia entre las alturas del campo más alto y el más bajo visitados mientras él entrega la correspondencia será igual a su cansancio. Ayúdelo y determine el más pequeño agotamiento para Gustavo mientras él entrega toda la correspondencia.
Entrada
La primera línea de la entrada contiene un entero . Las siguientes líneas representan campos en la correspondiente fila. El carácter \(‘P’\) aparecerá exactamente una vez, mientras el carácter \(‘K’\) aparecerá al menos una sola vez. Cada una de las siguientes líneas, contiene enteros positivos, las altitudes de los campos en las correspondientes filas. Esos valores son menores que .
Salida
La salida contiene en un línea simple solamente un entero, el cual representa el mínimo posible de cansancio.
Ejemplo # 1 de Entrada
2
P.
.K
2 1
3 2
Ejemplo # 1 de Salida
0
Ejemplo # 2 de Entrada
3
P..
.KK
...
3 2 4
7 4 2
2 3 1
Ejemplo # 2 de Salida
2
Ejemplo # 3 de Entrada
3
K.P
...
K.K
3 3 4
9 5 9
8 3 7
Ejemplo # 3 de Salida
5
Explicación del primer ejemplo: Comenzando en la oficina de correos, Gustavo puede moverse directamente al campo con la casa, entregar la correspondencia y regresar a la oficina de correos. Ya que el campo con la oficina de correo y el campo con la casa tienen la misma altitud, el cansancio de Gustavo es igual a cero.
Comments