Simulando el Juego de la vida X13387

El matemático inglés John Conway se inventó en 1970 el denominado "Juego de la vida": Imaginad una matriz cuadrada con n filas y n columnas, con posiciones libres y con posiciones ocupadas por una bacteria. El juego considera la evolución de las bacterias teniendo en cuenta reglas de interacción local.

En la matriz se consideran posiciones adyacentes a una posición las (como máximo ocho) posiciones que se encuentran a distancia 1, ya sea horizontalmente, verticalmente o en diagonal. En cada instante, cada posición de la matriz está vacía o contiene una bacteria. Las reglas son:

• Una posición vacía en un instante t contendrá una bacteria en el instante t + 1 si y sólo si en el instante t tenía exactamente tres bacterias adyacentes.
• Una posición ocupada en un instante t contendrá una bacteria en el instante t + 1 si y sólo si en el instante t tenía dos o más bacterias adyacentes.

Queremos hacer una simulación secuencial de la evolución del juego en la qué, en cada instante, sólo se actualiza una posición. La secuencia de posiciones sigue un recorrido en zig-zag por columnas, comenzando en la posición de arriba a la izquierda, (0,0), recorriendo la columna 0 de arriba a abajo ((0,0) a (n−1,0)), la columna 1 de abajo arriba ((n−1,1) a (0,1)), etc.

Llamamos vuelta a un recorrido completo de todas las posiciones de la matriz siguiendo el recorrido en zig-zag por columnas.

Escribid un programa que, dada la matriz inicial del juego y un número de vueltas, determine cuál es la matriz del juego después del número de vueltas de simulación estipulado.

Observad que, si después de una vuelta de simulación la matriz no ha cambiado, tampoco cambiará en las vueltas siguientes.

Entrada

La entrada está formada por dos números naturales n > 0, el tamaño de la matriz, y v>0, el número de vueltas, seguidos por una lista de posiciones de la matriz, pares de enteros entre 0 y n−1 , que indican las posiciones de la matriz donde hay bacterias.

Salida

Escribid la matriz inicial del juego y las matrices intermedias (después de cada vuelta) siguiendo el formato de los ejemplos.

Observación

Tened en cuenta que, si después de una vuelta la matriz del juego no ha cambiado, esta matriz nunca se tiene que escribir más de dos veces.