.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » light

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
light


Timp maxim de executie/test:
0.1 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

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
  • 1 < m <= 300
  • 1 < n <= 15
  • Pentru toate datele de test se problema are solutie.
  • Numarul de linii ale fisierului de iesire va fi <= 20000.
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


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

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la .campion 2007: perechi, teanc, index, copaci, teren, pizza, grupe, cod, ecran, drum, soldati, factura, palma, decript, lbd, aven, cs, h, trenuri, sort, spam, complex, parent, holo, tren2, gray, siruri, arce, pasi, cifre, mgo, firma, joc, cartonase, vikingi, anagrame, balbe, vecini, balaur, tribile, conflicte, criptmat, mesaj, maxim, magic3, desen, plimbare, cutie, patrate, party, vagoane, robot, astre, trains, numere2, friends, tricouri, furtuna, net, baby, scaune, 3d, axa, bile2, vmem, pahare, termen, sablon, zapada, cuvinte, excursie, hd, pajura, pc, sir, cadere, pioni
De acelaşi autor: sort, iepuras, pahare, turist, arthur, pento, cod2, game, ambigram, jokes, trecere, paianjen, zumzi, cifru3, pamant, pixy, triburi, culori1, cifre5, arc
Despre matrice: vopsea, harta, opmat, sarpe, magic2, tetris, origami, concurs, iepuras, tribile, criptmat, cutie, patrate, 3d, pajura, perspic, vecini2, livada, matrice3, kafka, erdos, grup, scor2, reteta2, rezervatie, scoici, tablou, game, stea, submatrix, cifru, jokes, oua, trecere, na, dotnet, renju, ghici, mere1, agitatie, lacuri, sotron, desen1, camion, ceas1, fibo, parc, excursia, matricea, zidar, joc6, log, concurs2, cladiri, dist, centru, robinson, cuburi2, joc8, joc9, romeo, adevar, soricel2, avere, joc11, vizibil, sah1, blockout, masina3, lsort, anticip, matrice1, evantai, spion, pereti, zumzi, roboti, placare, tabel, ocr, numere7, lacusta, becuri, sir5, flori, cartele, furnica, pavare, poarta, rj, peri, poligon2, sablon1, gradina, matrice4, poartas, balcon, submdisj, v, matrx, figura, neuroni, raze, roboti1, bila, iepurasi, colorare, mat, submatrix1, simetric1, plaja, xor2, guess, albine1, joct, alfabetar, stele, tablou1, alpinist, cladire, cri, grupe2, el, mahjong, sir9, acces, tort1, joc17, mesaj3, zar1, xy, poteci, avioane, broscute, safeu, acoperire1, radioactiv, robot4, lcdr, jb, slide, maxtri, dame, triunghi4, elicop, compresie, mijloc, cubulete, romb, medalion, bile6, zigzag, puncte5, intersectii, matd3, matrixdel, speed, seif1, traseu2, incadrare, betasah, zona, latin, zmax, amestec, sudoku1, gradina1, spider, zone, bemo, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
surse trimise | ajutor