Slikar P41955

!‘El maligno emperador Cactus ha conseguido la jarra mágica y ha inundado el bosque encantado! El Pintor y los tres puercoespines tienen que regresar a la guarida del Castor donde estarán a salvo del agua.

El mapa el Bosque Encantado consiste en $R$ filas y $C$ columnas. Los campos vacíos se representan con ’.’, los campos inundados con ’*’, y las rocas con ’X’. Adicionalmente, la guarida del Castor con ’D’ y el Pintor y los tres puercoespines con ’S’.

Cada minuto el Pintor y los tres puercoespines pueden moverse a uno de los cuatro campos vecinos (arriba, abajo, izquierda o derecha). Pero la inundación también se expande: cualquier campo que sea contiguo con al menos un campo inundado, se inunda en el minuto siguiente. Ni el agua, ni el Pintor con sus puercoespines pueden cruzar las rocas. El Pintor y los puercoespines no pueden cruzar los campos inundados, ni moverse a un campo que está a punto de ser inundado. Por otra banda, el agua no puede inundar la guarida del Castor.

Escribe un programa que, dado un mapa del Bosque Encantado, retorne la mínima cantidad de tiempo necesario para que el Pintor y los tres puercoespines puedan llegar a la guarida del Castor.

Entrada

La primera línea contiene dos enteros, $R$ y $C$, menores o iguales a 50. Las siguientes $R$ líneas contienen $C$ caracteres ’.’, ’*’, ’X’, ’D’, ’S’. El mapa contendrá exactamente un único caracter ’D’ y un único caracter ’S’.

Salida

Escribe una línea con la mínima cantidad de tiempo que necesitan el Pintor y los tres puercoespines para llegar a la guarida del Castor. Si esto no es posible, escribe una línea con la palabra KAKTUS.