Rompiendo el KAPTCHA

Un CAPTCHA es un sistema utilizado por algunos sitios web para determinar si un usuario es un humano o un programa automatizado. Con el auge de la inteligencia artificial, algunos programas han empezado a ser capaces de superar estas pruebas. Por ello, en los últimos años su dificultad ha aumentado considerablemente. En este contexto, una famosa multinacional ha diseñado el King Automated Public Turing test to Tell Computers and Humans Apart (KAPTCHA), el CAPTCHA definitivo, creado para impedir que cualquier autómata pueda suplantar la identidad de un ser humano. En esta prueba se te proporciona un laberinto representado mediante una cuadrícula bidimensional. Cada celda de la cuadrícula contiene un carácter ASCII. El recorrido debe comenzar en una celda que contenga el carácter \(k\) y terminar en una celda que contenga el carácter \(K\). El objetivo es maximizar la puntuación ASCII obtenida durante el recorrido. La puntuación inicial es 0. Cada vez que visitas una celda por primera vez, se suma a tu puntuación el valor del código ASCII del carácter contenido en dicha celda. Los movimientos dentro del laberinto están restringidos. Desde una celda puedes moverte únicamente a celdas adyacentes (arriba, abajo, izquierda o derecha) que cumplan al menos una de las siguientes condiciones: <ul class="list-disc list-inside"> <li>La celda de destino contiene el mismo carácter que la celda actual.</li> <li>El movimiento entre ambos caracteres está definido como movimiento válido.</li> </ul>Para asegurarse de que no eres un robot, el sistema KAPTCHA pide que calcules la mejor puntuación posible. ## Entrada La entrada contiene un único caso de prueba. Primero aparecen varias líneas, todas de la misma longitud, que representan el laberinto ASCII. La descripción del laberinto termina con una línea en blanco. A continuación aparecen varias líneas que describen los movimientos válidos entre caracteres. Se garantiza que el laberinto no tendrá más de 1000 filas ni 1000 columnas. ## Salida Se debe imprimir un único número entero: la mejor puntuación ASCII que puede obtenerse comenzando en cualquier celda con \(k\) y terminando en cualquier celda con \(K\). En el caso de que no exista ningún camino válido, se debe imprimir -1.

akbbKd
aceddd
eeeeff
ffgggg
kxxxxK

k -> a
a -> e
e -> d
e -> g
g -> x
d -> K

1281