light

Lights Out este un joc creat de firma americana Hasbro. Jocul consta dintr-o matrice de dimensiune 5x5, fiecare casuta a matricei continānd un bec. La īnceputul jocului o parte dintre beculete sunt aprinse. Scopul jocului este de a stinge toate beculetele de pe tabla. Pentru aceasta se pot apasa pe rānd anumite beculete ale matricei. La apasarea unui beculet se va modifica starea beculetului respectiv, dar si starea celor patru beculete adiacente cu acesta orizontal sau vertical. Astfel daca unul din cele cinci beculete era aprins el se va stinge, iar daca era stins se va aprinde. Īn figura urmatoare se vede care este efectul apasarii beculetului de pe linia 2 coloana 3 a matricei. Īn aceasta figura am codificat cu 1 beculetele aprinse si cu 0 beculetele stinse, si am marcat cu gri casutele afectate de apasarea beculetului.

1

0

1

1

0

1

0

0

1

0

0

0

1

0

1

0

1

0

1

1

1

0

0

0

0

1

0

1

0

0

1

1

0

1

0

1

1

0

1

0

0

0

0

0

1

0

0

0

0

1
De observat ca apasarea unui beculet de pe marginea matricei va modifica starea a numai 3 sau 4 beculete.
Pentru problema de fata va propunem o generalizare a acestui joc, īn care matricea este formata din m linii si n coloane de beculete.

Cerinta
Fiind date dimensiunile m si n ale matricei si starea initiala a celor mxn beculete, se cere sa determinati o succesiune de beculete care trebuie sa fie actionate pentru ca īn final toate becurile sa fie stinse.

Date de intrare
Fisierul de intrare light.in contine pe prima linie doua numere naturale separate printr-un spatiu, reprezentānd dimensiunile matricei de joc. Urmatoarele m linii ale fisierului vor contine cāte n cifre binare (0 si 1) separate prin cāte un spatiu, reprezentānd starea fiecarui beculet de pe tabla de joc. Un beculet aprins este codificat cu 1 iar un beculet stins cu 0

Date de iesire
Fisierul de iesire light.out pe fiecare linie a sa cāte o pereche de cāte doua numere naturale x si y, reprezentānd linia si respectiv coloana unui beculet ce trebuie actionat. Liniile sunt numerotate incepand cu 1 de sus īn jos, iar coloanele sunt numerotate īncepānd cu 1 de la stānga la dreapta. Ordinea īn care sunt actionate beculetele nu are importanta. Daca problema are mai multe solutii, se va accepta oricare dintre aceste solutii.

Restrictii Exemplu
light.in light.out

4 4
 0 0 0 1
0 0 1 1
0 0 1 1
0 1 1 1

 4 3
2 4
Timp maxim de executie/test : 0.1 secunde 


prof. Popescu Carmen
Colegiul National "Gheorghe Lazar" Sibiu
carmen_cngl@yahoo.com