|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
ultima problemă
grupă: mică
sursă: OMI 2016 ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
|
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.
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
propunător: Prof. Emanuela Cerchez emanuela.cerchez@gmail.com Probleme recomandate
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| surse trimise | ajutor |