Gra w życie

Wyobraźmy sobie nieskończoną płaszczyznę podzieloną na kratki. Każda kratka jest komórką, która może być żywa (oznaczana jako czarna) lub martwa (biała). Na początku definiujemy, jakie komórki będą żywe, jakie martwe, a następnie układ samodzielnie ewoluuje zgodnie z następującymi zasadami:

• jeżeli komórka jest żywa, ale ma więcej niż trzech sąsiadów, umiera z przeludnienia (za sąsiadów komórki uznajemy 8 komórek dookoła niej)
• jeżeli komórka jest żywa, ale ma mniej niż 2 sąsiadów, umiera z "niedoludnienia"
• jeżeli komórka jest martwa, ale ma dokładnie trzech żywych sąsiadów, sąsiedzi ci rozmnażają się i komórka staje się żywa
• w każdej innej sytuacji stan komórki się nie zmienia.

Opisane wyżej zasady zostały wymyślone w 1970 przez matematyka Johna Conwaya i noszą nazwę gry w życie.

Na potrzeby tego zadania przyjmijmy, że gra toczy się na planszy 100 x 100. W załączonym pliku znajduje się spis komórek, które na początku są żywe (każda linia to współrzędne pojedynczej komórki, np. 23 42 oznacza, że żywa jest komórka w 23 wierszu i 42 kolumnie, przy czym numerowanie wierszy i kolumn zaczyna się - jak w większości języków programowania - od zera). Sprawdź, po ilu krokach układ wymrze, tj. nie będzie w nim żadnej żywej komórki.