Nu aveți permisiuni pentru a descărca fișierul grader_test8.ok

Fișierul intrare/ieșire becuri.in, becuri.out Sursă ad-hoc
Autor Adăugată de avatar heracle Radu Muntean heracle
Timp de execuție pe test 0.3 sec Limită de memorie 512 KB
Scorul tău N/A Dificultate N/A

Becuri

La un muzeu din orasul nostru, gardianul, imediat dupa inchiderea muzeului, trebuie sa stinga toate luminile din camera principala. Patronul, observand consumul de curent mult prea mare al muzeului, s-a hotarat sa nu mai aprinda toate luminile in fiecare camera, ci doar cateva pentru a nu ramane pe intuneric.
Camera principala are forma dreptunghiulara(de matrice) si contine becurile unul langa altul, aliniate pe l linii si c coloane. Stiind ca exista l+c comutatoare(dispuse la capatul fiecarei coloane sau linii) care schimba starea tuturor becurilor de pe linia sau coloana la care este distribuit, gardianul vrea sa determine numărul minim de actionări de comutatoare astfel incat în final toate becurile de pe panou sa fie stinse, dacă acest lucru este posibil.

Prin schimbarea starii întelegem trecerea din starea in care se afla în starea opusa (stins → aprins, aprins → stins).

Date de intrare

Fișierul de intrare becuri.in are pe prima linie două numere naturale separate prin spațiu l și c reprezentând numărul de linii, respectiv numărul de coloane ale panoului publicitar.
Următoarele l linii vor conține câte c întregi separați prin câte un spațiu, fiecare întreg reprezentând starea inițială a unui bec, 1 dacă becul este aprins și 0 dacă acesta este stins.

Date de ieșire

Fișierul de ieșire becuri.out va conține o singură linie pe care se va scrie un întreg ce reprezintă numărul minim de acționări de comutatoare pentru a stinge toate becurile, sau -1 dacă pentru configurația inițială dată nu există soluție.

Restricții

1<l,c<20;

Exemplu

becuri.in becuri.out
4 4
1 1 0 1
0 0 1 0
0 0 1 0
1 1 0 1
3
becuri.in becuri.out
4 4
1 1 0 1
0 0 1 0
0 0 1 0
0 0 0 0
-1

Explicație

apasand intrerupatorul liniei 1 si 4 vom obtine

0 0 1 0
0 0 1 0
0 0 1 0
0 0 1 0

apasand intrerupatorul coloanei 3 se vor stinge toate becurile

Trebuie să te autentifici pentru a trimite soluții. Click aici