El Caballo
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 y con Slavko a ciegas, hace exactamente 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 está desbloqueada sólo durante 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 . En cada segundo Mirko tiene que hacer un movimiento (seleccionando uno de los 8 movimientos en forma de 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 movimientos.
Entrada
La primera línea de la entrada contiene dos enteros positivos, , el tamaño del tablero y , el número de movimientos que Mirko hará. La segunda línea contiene dos enteros positivos y , los índices de la fila y la columna de la casilla inicial del caballo seleccionada por Mirko. Las próximas líneas contienen cada una N enteros positivos menores que , los valores de en las correspondientes casillas.
Salida
La primera línea de la salida debe contener el entero no negativo , el número de casillas que el caballo puede posiblemente ocupar después de 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