«Կյանք» խաղը

«Կյանք» խաղը մաթեմատիկոս Ջոն Քոնուեյի ստեղծած բջջային ավտոմատ է։ Այն իրական “խաղ” չէ՝ խաղացողներ կամ գնդակներ չունի․ պարզապես կանոնների մի համակարգ է, որտեղ որոշվում է՝ որ բջիջները կապրեն, կմեռնեն կամ կծնվեն հաջորդ փուլում։
Խաղը հետաքրքիր է նրանով, որ շատ պարզ կանոններից առաջանում են բարդ և երբեմն անսպասելի պատկերներ։

Խաղը տեղի է ունենում անսահման քառակուսային ցանցի վրա․
յուրաքանչյուր վանդակ կարող է լինել

• կենդանի (պարունակել բջիջ)

• մեռած (դատարկ)

Յուրաքանչյուր քայլում բոլոր վանդակները միաժամանակ փոփոխվում են՝ հետևելով այս կանոններին․

Ամեն վանդակ ունի 8 հարևան (վերև, ներքև, ձախ, աջ և անկյունայիններ)։ Դրանց հիման վրա գործում են այս կանոնները.

1. Ծնունդ

Եթե դատարկ վանդակ ունի ճիշտ 3 կենդանի հարևան, ապա այնտեղ ծնվում է՝ բջիջ, այն դառնում է կենդանի։

2. Գերբնակեցում

Եթե կենդանի բջիջն ունի ավելի քան 3 կենդանի հարևան, այն մահանում է։

3. Մենակություն

Եթե կենդանի բջիջն ունի 2-ից քիչ կենդանի հարևան, այն նույնպես մահանում է։

4. Հաստատունություն (Survival)

Եթե կենդանի բջիջն ունի ճիշտ 2 կամ 3 կենդանի հարևան, ապա այն շարունակում է ապրել։

Տրված է «Կյանք» խաղի ինչ-որ մի դրվագ՝ բջիջների համայնք։ Պահանջվում է գրել ծրագիր, որը հաշվի և տպի, թե հաջորդ պահին ինչ տեսք կունենա բջիջների համայնքը։

Մուտքային տվյալներ

Առաջին տողում տրված են վանդակավոր դաշտի չափերը ։ Հաջորդ տողերից յուրաքանչյուրում տրված են հատ 0-ներ և 1-եր։ 1-ը նշանակում է, որ տվյալ վանդակում կյանք կա, 0-ն նշանակում է, որ չկա։

Ելքային տվյալներ

Ելքում պետք է արտածել վանդակավոր դաշտի պատկերը մեկ քայլ հետո, այսինքն դաշտի չափերը, այնուհետև պետք է արտածել տող, յուրաքանչյուրում հատ 0-ներ և 1-եր։

Օրինակ

5 6
000100
001100
001000
000000
010100

5 6
001100
001100
001100
001000
000000