Fişierul intrare/ieşire:becuri.in, becuri.outSursăLot Ploiesti 2006
AutorCosmin Silvestru NegruseriAdăugată debogdan2412Bogdan-Cristian Tataroiu bogdan2412
Timp execuţie pe test0.05 secLimită de memorie20096 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Becuri

Un panou publicitar de forma dreptunghiulara contine becuri, unul langa altul, aliniate pe N linii si M coloane.
Fiecare bec are asociat un comutator. Prin actionarea comutatorului unui bec se schimba starea tuturor becurilor de pe linia lui si de pe coloana lui, in afara de starea sa. Prin schimbarea starii intelegem trecerea din starea in care se afla in starea opusa (stins → aprins, aprins → stins).

Cerinta

Sa se realizeze un program care determina numarul minim de actionari de comutatoare astfel incat in final toate becurile de pe panou sa fie stinse, daca acest lucru este posibil.

Se cere si setul de actionari care stinge toate becurile.

Date de intrare

Fisierul de intrare becuri.in are pe prima linie doua numere naturale separate prin spatiu N si M reprezentand numarul de linii, respectiv numarul de coloane ale panoului publicitar.

Urmatoarele N linii vor contine cate M intregi separati prin cate un spatiu, fiecare intreg reprezentand starea initiala a unui bec, 1 daca becul este aprins si 0 daca acesta este stins.

Date de iesire

Fisierul de iesire becuri.out va contine pe prima linie un numar intreg MIN ce reprezinta numarul minim de actionari de comutatoare pentru a stinge toate becurile, sau -1 daca pentru configuratia initiala data nu exista solutie.

In cazul existentei unei solutii fiecare din urmatoarele MIN linii va contine cate 2 numere reprezentand coordonatele comutatoarelor actionate.

Restrictii

  • 1 ≤ N, M ≤ 500

Exemplu

becuri.inbecuri.out
3 3
0 0 1
0 0 1
1 1 0
1
3 3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content