El Caballo


Submit solution

Points: 100 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

Mirko y Slavko son amigos de los azucareros del centro y juegan el popular juego conocido como El Caballo. Mirko coloca un caballo de ajedrez en un tablero NxN y con Slavko a ciegas, hace exactamente T movimientos, uno por segundo. Después de esto, Slavko tiene que adivinar la posición final del caballo para ganar.

El tablero de este juego es inusual ya que cada casilla está bloqueada parte del tiempo. Más precisamente, cada casilla está marcada con un entero positivo. Una casilla con el número K está desbloqueada sólo durante 0, K, 2K, 3K, ... segundos; esta está bloqueada en todos los otros tiempos. El caballo, por supuesto, puede ocupar una casilla sólo mientras esté desbloqueada.

El juego comienza en el segundo 0. En cada segundo Mirko tiene que hacer un movimiento (seleccionando uno de los 8 movimientos en forma de L posibles, dos casillas en una dirección y una en la otra, como en las reglas estándar del juego), garantizando que la casilla de destino no está bloqueada durante el próximo segundo. Ayude a Slavko a escribir un programa para calcular todas las posibles casillas que el caballo puede ocupar después de T movimientos.

Entrada

La primera línea de la entrada contiene dos enteros positivos, N (3 \le N \le 30), el tamaño del tablero y T (1 \le T \le 1 000 000), el número de movimientos que Mirko hará. La segunda línea contiene dos enteros positivos X y Y (1 \le X, Y \le N), los índices de la fila y la columna de la casilla inicial del caballo seleccionada por Mirko. Las próximas N líneas contienen cada una N enteros positivos menores que 10^9, los valores de K en las correspondientes casillas.

Salida

La primera línea de la salida debe contener el entero no negativo M, el número de casillas que el caballo puede posiblemente ocupar después de T movimientos. Las próximas M líneas deben contener los índices de estas casillas, ordenadas crecientemente por el índice de la fila, con casillas de igual fila ordenadas crecientemente por el índice de la columna.

Ejemplo #1 de Entrada

3 2 
1 1 
1 3 2 
2 3 2 
3 1 1

Ejemplo #1 de Salida

2 
1 1 
1 3

Ejemplo #2 de Entrada

5 6 
2 3 
4 5 3 2 3  
1 3 4 3 1  
3 4 1 3 2  
4 4 2 1 3  
4 6 4 9 2

Ejemplo #2 de Salida

5 
1 4 
2 1 
2 5 
4 5 
5 2

Ejemplo #3 de Entrada

3 3 
2 2 
3 6 4  
2 2 5  
1 3 7

Ejemplo #3 de Salida

0

Descripción del primer ejemplo: Debajo se muestra el estado del tablero en cada segundo. Las casillas desbloqueadas están denotadas por ‘.’, las bloqueadas por ‘#’ y todas las posibles localizaciones del caballo por \(‘K’\).

Segundo 0

K..
...
...

Segundo 1

.##
###
#K.

Segundo 2

K#K
.#.
#..

Comments

There are no comments at the moment.