Warp-world P13924


Statement
 

pdf   zip

thehtml

Warp-world es un mundo rectangular donde puedes desplazarte caminando (avanzas unas casilla en cualquiera de las cuatro direcciones en un segundo) o usando warp-points: puntos del mundo, representados por una letras, que te permiten teletransporte a cualquier otro punto con la misma letra en tan solo un segundo. Por ejemplo, en el siguiente warp-world

D.....A..
..A....B.
.........
........A
2.....C.C
B.......1

para desplazarte del punto 1 al punto 2 puedes caminar (9 segundos: 8 pasos horizontales y uno vertical) o bien avanzar dos pasos al norte (ignorando el warp-point C), teletransportarte a la casilla A de la primera fila, avanzar un paso al sur y uno al este, teletransporte a la casilla B de la última fila, y avanzar un paso al norte, para un total de 2+1+2+1+1=7 segundos. Observa que el warp-point A tiene 3 puntos de entrada, y que el warp-point D es completamente inútil.

Se te pide que, dado un cierto warp-world, respondas cuál es el mínimo número de segundos necesarios para desplazarte entre varios pares de puntos 1 y 2, como en el ejemplo anterior.

Entrada

Cada entrada empieza con la descripción de un único warp-world: el número F de filas y C columnas del warp-world en una línea, seguido de F líneas de C caracteres cada una, describiendo un warp-world con no más de 26 tipos de warp-points A-Z (el número de warp-points en la entrada es arbitrario). A continuación k preguntas, cada una de las cuales ocupa una línea y consiste de las coordenadas (fila y columna, empezando por 1) del punto 1 y del punto 2, separadas entre si por dos espacios.

Salida

Para cada pregunta, escribe una línea con el mínimo número de segundos necesarios para desplazarte del punto 1 al punto 2 del warp-world.

Puntuación

  • TestA:  ‍ Entradas con F,C≤ 50 y k<10 preguntas.  ‍25 Puntos ‍
  • TestB:  ‍ Entradas con F,C≤ 100 y k<100 preguntas.  ‍25 Puntos ‍
  • TestC:  ‍ Entradas con F,C≤ 200 y k<1000 preguntas.  ‍25 Puntos ‍
  • TestD:  ‍ Entradas con F,C≤ 400 y k<10000 preguntas.  ‍25 Puntos ‍
Public test cases
  • Input

    1 25
    ..A...A..B.....B.C....C..
    1 1  1 25
    1 25  1 1
    1 4  1 25
    1 8  1 25
    

    Output

    12
    12
    11
    8
    
  • Input

    6 11
    C.A..A....B
    .A.BA....B.
    ..BA....B..
    .BA....B..A
    B.....B..A.
    .....B..A.C
    1 1  6 11
    3 3  6 1
    3 3  5 11
    6 3  6 3
    6 3  5 4
    6 10  1 10
     

    Output

    1
    2
    3
    0
    2
    5
    
  • Input

    6 9
    D.....A..
    ..A....B.
    .........
    ........A
    ......C.C
    B........
    6 9  5 1
    5 1  5 9
    5 3  5 9
    

    Output

    7
    6
    5
    
  • Information
    Author
    Omer Giménez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++