Simulant el Joc de la vida X13387

El matemàtic anglès John Conway es va inventar l’any 1970 l’anomenat "Joc de la vida": Imagineu una matriu quadrada amb $n$ files i $n$ columnes amb posicions lliures i amb posicions ocupades per un bacteri. El joc considera l’evolució dels bacteris amb regles locals.

A la matriu es consideren posicions adjacents a una posició les (vuit, com a molt) posicions que és troben a distància 1, ja sigui horitzontalment, verticalment o bé en diagonal.

En cada instant, cada posició de la matriu està buida o conté un bacteri. Les regles són:

• Una posició buida en un instant $t$ contindrà un bacteri en l’instant $t + 1$ si i només si en l’instant $t$ tenia exactament tres bacteris adjacents.

• Una posició ocupada en un instant $t$ contindrà un bacteri en l’instant $t + 1$ si i només si en l’instant $t$ tenia dos o mes bacteris adjacents.

Volem fer una simulació seqüencial de l’evolució del joc en la qual a cada instant només s’actualitza una posició. La seqüència de posicions és un recorregut de la matriu en ziga-zaga per columnes. El recorregut comença a la posició de dalt a l’esquerra, la $(0,0)$, recorre la columna 0 de dalt a baix ($(0,0)$ a $(n-1,0)$), la columna 1 de a baix a dalt ($(n-1,1)$ a $(0,1)$), etc.

 
Anomenem volta a un recorregut complet de totes les posicions de la matriu seguint una ziga-zaga per columnes.

 
Feu un programa que, donada la matriu del joc i el nombre de voltes, determini quina serà la matriu del joc després de simular el joc per el nombre de voltes indicat.

 
Observeu que, en cas de que despés d’una una volta la matriu sigui la mateixa que abans de la volta, la matriu no canviarà mai.

Entrada

La entrada està formada por dos nombres naturals $n$, la dimensió de la matriu, i $v$, el nombre de voltes. Després tenim la descripció de la situació inicial del joc indicat per una llista de posicions, parells d’enters entre $0$ i $n-1$, indicant les posicions dels bacteris.

Sortida

Escriviu la matriu inicial del joc i totes les matrius intermitjes (la matriu del joc després de cada volta), amb una linea en blanc després de cada matriu. Seguiu el format dels exemples.

Observació

Teniu en compte que si després d’una volta la matriu del joc no ha canviat no s’ha de escriure aquesta matriu més de dos cops.