Fișierul intrare/ieșire	numere12.in, numere12.out	Sursă	Stelele Informaticii 2003, clasele 9-10 (Infoarena)
Autor	Bogdan Stroe	Adăugată de	Teodor Plop • teodor94
Timp de execuție pe test	0.05 sec	Limită de memorie	20096 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Numere12 (clasele 9-10)

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 aceeasi paritate, efectuand un numar minim de mutari.

Date de intrare

Pe prima linie a fisierul de intrare numere12.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 numere12.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