¡Caballos! P81316


Statement
 

pdf   zip

thehtml

¡Los caballos inundan el tablero de ajedrez! Hemos dejado a k de ellos repartidos por un tablero rectangular de tamaño n× m, y te pedimos que calcules, para cada casilla del tablero, de cuántos modos es posible mover cualquiera de los k caballos para llegar a la casilla en exactamente t saltos. (Suponemos que sabes que el caballo es una ficha que hace saltos en forma de L, avanzando dos casillas en una dirección cualquiera y otra en una dirección perpendicular a la anterior. Si tienes cualquier duda, ¡pregunta!).

Por ejemplo, en el tablero siguiente,

||

    X
C1    
C2C2C2C2C2
     

||

el caballo marcado como C1 puede llegar a X en 3 saltos de exactamente 3 modos (dos de ellos, por cierto, ocupando la casilla donde está C2 antes de llegar a X). En cambio, el caballo C2 puede llegar a X en 3 saltos de 6 modos distintos (de los 6, en 4 de ellos hace un salto que luego deshace, y a continuación salta a X; de los 6, en 2 de ellos pasa por X antes de acabar en X: eso está permitido). Por lo tanto, hay 9 modos de llegar a la casilla X.

Te pedimos que calcules el número total de modos de llegar a cada una de las casillas del tablero en t saltos.

Entrada

Cada entrada empieza con el número 0<c≤ 20 de casos. Cada caso se da en una línea, con los números n,m≥ 3, k>0 y t≥ 0 separados por espacios, y k líneas con las coordenadas iniciales de los k caballos: dos números entre 1 y n (fila) y entre 1 y m (columna). Se te garantiza que las dimensiones del tablero n y m no serán mayores de 100, y que t será menor de 100. El número k de caballos será inferior a 10000. Además, podría pasar que varios caballos ocuparan la misma casilla inicial: en tal caso, usar cada uno de ellos contabilizaría como un modo distinto de llegar a la casilla objetivo.

Salida

Para cada caso, escribe n filas de m números cada una, separados por comas, con el número de modos de llegar a la casilla correspondiente. Se entiende que el primer número de la primera fila corresponde a la casilla (1,1), y que el último número de la última fila corresponde a la casilla (n,m). Si el número que debieras escribir es mayor que 108, escribe >1e8. Escribe tres guiones --- después de cada caso de pruebas.

Puntuación

Hay 10 entradas. Tu programa recibirá 10 puntos por cada entrada resuelta. Las dimensiones n,m de la entrada i-ésima no serán mayores de 3, 4, 5, 7, 10, 20, 30, 50, 70, 100. Además, el número k será 1 en las primeras 3 entradas, menor que 10 en las siguientes 3 entradas, y menor que 10000 en las restantes 4 entradas. Además, el número t será menor que 3,4,5,7 y 10 en las primeras 5 entradas, y menor que 100 en las restantes 5.

Prueba: Final OIE-10
Autor: Omer Giménez

Public test cases
  • Input

    5
    3 3 1 0
    1 1
    3 3 1 1
    1 1
    3 3 1 2
    1 1
    3 3 1 3
    1 1
    3 3 1 1
    2 2
    

    Output

    1,0,0
    0,0,0
    0,0,0
    ---
    0,0,0
    0,0,1
    0,1,0
    ---
    2,0,1
    0,0,0
    1,0,0
    ---
    0,1,0
    1,0,3
    0,3,0
    ---
    0,0,0
    0,0,0
    0,0,0
    ---
    
  • Input

    2
    4 5 2 3
    2 1
    3 4
    4 5 3 3
    2 1
    3 4
    3 4
    

    Output

    5,0,16,0,9
    0,11,0,5,0
    5,0,14,0,6
    0,14,0,8,0
    ---
    8,0,24,0,15
    0,18,0,7,0
    8,0,19,0,10
    0,22,0,12,0
    ---
    
  • Input

    3
    3 7 1 17
    1 1
    3 7 1 18
    1 1
    3 7 1 19
    1 1
    

    Output

    0,30966528,0,40933440,0,31041912,0
    25452160,0,38868872,0,38498680,0,25712512
    0,30971272,0,40939968,0,31046400,0
    ---
    69840144,0,>1e8,0,>1e8,0,69545080
    0,81873408,0,>1e8,0,81873408,0
    69835400,0,>1e8,0,>1e8,0,69540592
    ---
    0,>1e8,0,>1e8,0,>1e8,0
    >1e8,0,>1e8,0,>1e8,0,>1e8
    0,>1e8,0,>1e8,0,>1e8,0
    ---
    
  • Information
    Author
    Omer Giménez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++