Un panou publicitar de formă dreptunghiulară conţine becuri, unul lângă altul, aliniate pe n linii şi m coloane.
Fiecare bec are asociat un comutator. Prin acţionarea comutatorului unui bec se schimbă starea tuturor becurilor de pe linia lui şi de pe coloana lui, în afară de starea sa. Prin schimbarea stării înţelegem trecerea din starea în care se află în starea opusă (stins → aprins, aprins → stins).
Cerinţă
Să se realizeze un program care determină numărul minim de acţionări de comutatoare astfel încât în final toate becurile de pe panou să fie stinse, dacă acest lucru este posibil.
Date de intrare
Fişierul de intrare becuri.in are pe prima linie două numere naturale separate prin spaţiu n şi m reprezentând numărul de linii, respectiv numărul de coloane ale panoului publicitar.
Următoarele n linii vor conţine câte m î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.