Cerința

In anii ’70, John Horton Conway un renumit matematician britanic a inventat un model ce simulează evoluția unei populații de viruși. Acest automat “celular” funcționează având la bază un număr de patru reguli și se desfășoară pe o suprafață bidimensională infinită.

Neavând la dispoziție o infinitate de locații de memorie, vă propunem să rezolvați această problemă pentru o matrice pătratică de dimensiune n. Această matrice este înconjurată de raze ultraviolete ce omoară instantaneu orice celulă vie (bordați matricea cu zerouri pe care nu le modificați niciodată).

Regulile după care funționează automatul sunt următoarele:

• Orice celulă vie ce are mai puțin de două celule vii vecine va muri din singurătate.
• Orice celulă vie cu doi sau trei celule vii vecine va supraviețui și se va regăsi în următoarea generație.
• Orice celulă vie cu mai mult de trei vecini (celule vii) va muri din cauza suprapopulării.
• O poziție din matrice ce nu este ocupată de o celulă vie dar care are exact trei vecini (celule vii) se va popula în generația următoare (reproducere).

O localție din matrice poate avea maxim 8 vecini.

Date de intrare

Fișierul de intrare conway.in conține pe prima linie numărul n reprezentând dimensiunea matricei pătratice pe care se desfășoară jocul împreună cu o valoare g reprezentând numărul de generații ce vor fi calculate. In continuare va fi dată matricea inițială – generația 0.

Date de ieșire

Fișierul de ieșire conway.out va conține matricea pătratică de dimensiune n reprezentând generația g în care o celulă vie este codificată cu valoarea 1, iar o locație liberă este codificată cu valoarea 0.

Restricții și precizări

• 1 ≤ n ≤ 100
• 1 ≤ g ≤ 20

Exemplu:

conway.in

4 2
1 1 0 0
0 1 0 0
0 0 1 1
0 0 0 0

conway.out

1 1 0 0 
1 0 1 0 
0 1 0 0 
0 0 0 0 

Explicație

Se cere a două generație plecând de la matricea inițială. Iată cele trei generații (0, 1 și 2):

1 1 0 0       1 1 0 0       1 1 0 0
0 1 0 0  >>>  1 1 0 0  >>>  1 0 1 0
0 0 1 1       0 0 1 0       0 1 0 0
0 0 0 0       0 0 0 0       0 0 0 0

Dacă am indexa această matrice de la 1 până la 4 și ne uităm cum evoluează populația celulară de la generația 0 (inițială) la generația 1, se observă cum celula de pe linia 2 și coloana 1 va fi populată deoarece are exact 3 vecini, iar cea de pe linia 3 și coloana 4 moare deoarece are un singur vecin.