becuri

Becuri

== include(page="template/taskheader" task_id="becuri") ==

Poveste si cerinta...

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).
 
h2. 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.

h2. 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.

h2. 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.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ N, M ≤ 500$

h2. Exemplu
table(example). |_. becuri.in |_. becuri.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3 3
0 0 1
0 0 1
1 1 0
| 1
3 3

|

h3. Explicatie

== include(page="template/taskfooter" task_id="becuri") ==
 

...
== include(page="template/taskfooter" task_id="becuri") ==

1793