Fişierul intrare/ieşire:numere3.in, numere3.outSursăStelele Informaticii 2003, clasele 9-10
AutorBogdan StroeAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.05 secLimită de memorie20096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Numere 3

Ionel are o slabiciune pentru jocurile de perspicacitate. El incearca sa rezolve un astfel de joc in care are o matrice de dimensiune M x N ale carei elemente sunt numere intregi. O mutare consta in scaderea dintr-un element a numarului de vecini ai pozitiei elementului respectiv si cresterea cu unu a valorilor elementelor vecine. Vecinii pentru o anumita pozitie sunt elementele de pe orizontala si verticala, deci o pozitie poate avea 2, 3 sau 4 vecini. Anumite pozitii cunoscute din matrice sunt sensibile la scadere, adica nu se pot efectua mutari in pozitiile respective. Numarul acestor pozitii este egal cu K. Scopul lui Ionel este ca, pornind de la matricea initiala, sa obtina o matrice in care toate elementele sa aiba aceiasi paritate, efectuand un numar minim de mutari.

Date de intrare

Pe prima linie a fisierul de intrare numere3.in se afla trei numere, M, N si K cu specificatiile din enunt. Pe urmatoarele M linii se afla cate N numere intregi, reprezentand matricea initiala. Pe urmatoarele K linii se afla cate doua numere intregi separate printr-un spatiu, reprezentand coordonatele pozitiilor sensibile la scadere (primul numar reprezinta linia, al doilea coloana).

Date de iesire

In fisierul de iesire numere3.out se va afisa pe prima linie numarul minim de mutari MIN care rezolva jocul. Pe urmatoarele MIN linii se vor afisa mutarile, cate o mutare pe linie (doua numere intregi reprezentand linia si coloana mutarii). In cazul in care nu exista solutie, se va afisa -1.

Restrictii

  • 2 ≤ M, N ≤ 12
  • 0 ≤ K ≤ M*N
  • elementele din matrice sunt numere intregi cuprinse intre 1 si 10000 inclusiv, pe parcursul jocului insa, valorile din matrice se pot afla in afara acestui interval
  • daca exista mai multe solutii, se va afisa oricare

Exemplu

numere3.innumere3.out
2 2 1
2 1
1 2
2 1
1
1 1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content