¡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++