Chuck y la patada voladora (1) P61348

—Luces, cámara... ¡Acción!— grita Aaron.

Su hermano Chuck, que intrepreta a un famoso Ranger de Texas, está en la posición marcada con una C, mientras que el malvado de turno ocupa la posición marcada con una X. Entre Chuck y el malo hay muchos matones (todos ellos letras minúsculas), que basicamente están puestos para que Chuck pueda lucirse pegando patadas voladoras de karate mientras se desplaza hacia el malo. Por exigencias del guión, Chuck tiene prohibido avanzar más de k casillas (horizontal, vertical o diagonalmente) sin arrear a alguien.

El objetivo de Chuck es arrear una patada voladora al malo malote lo antes posible. Desplazarse una casilla cuesta 1 décima de segundo, tanto si la casilla está libre como si está ocupada. Cada patada voladora, incluyendo la última y definitiva, requiere exactamente 2 segundos (20 décimas). No es necesario que Chuck pegue una patada voladora cada vez que pasa por una casilla con un malo: basta con que lo haga al menos una vez cada k pasos.

Te pedimos que calcules cuál es el mínimo tiempo que requiere Chuck para desplazarse hasta el malo de turno y pegarle una patada voladora, incluyendo el tiempo que requiere dicha patada.

Entrada

La primera línea de la entrada contiene las dimensiones n y m (filas y columnas) del escenario, y el número k de casillas que puede avanzar Chuck (horizontal, vertical o diagonalmente) sin pegar a alguien. A continuación, n líneas de M caracteres cada una, con una única letra C (Chuck), una única letra X (el malvado), caracteres punto . (espacios vacíos) y letras minúsculas (los matones en los que Chuck tiene que apoyarse para llegar a su objetivo).

Salida

Escribe una línea con un único número: el mínimo número de décimas de segundo que Chuck necesita para llegar hasta el malo y pegarle una patada voladora. Si es imposible llegar al malo sin cumplir las exigencias del guión, escribe −1. En ambos casos, acaba la entrada con un salto de línea.

Puntuación

• Test1:  20 Puntos 

  Resolver entradas con n, m ≤ 10, k≤ 4.

• Test2:  20 Puntos 

  Resolver entradas con n, m ≤ 25, k≤ 5.

• Test3:  20 Puntos 

  Resolver entradas con n, m ≤ 50, k≤ 6.

• Test4:  10 Puntos 

  Resolver entradas con n, m ≤ 100, k≤ 10.

• Test5:  10 Puntos 

  Resolver entradas con n, m ≤ 100, k≤ 30.

• Test6:  10 Puntos 

  Resolver entradas con n, m ≤ 100, k≤ 60.

• Test7:  10 Puntos 

  Resolver entradas con n, m ≤ 100, k≤ 100.