== include(page="template/taskheader" task_id="tower8") ==
Poveste şi cerinţă...
Dispozitivul de apărare al elfilor are forma unei matrice cu $N$ linii şi $M$ coloane. În fiecare poziţie a matricei se plasează câte un turn de aparare după reguli bine stabilite. Cât timp există poziţii neocupate de un turn, se alege o astfel de poziţie şi se plasează acolo un turn de nivel $1$. Numim această operaţiune plasare. În funcţie de configuraţia poziţiilor vecine (pe $8$ direcţii) turnul va trece la un nivel superior. Atunci când un turn atinge nivelul $X$ şi are cel puţin un vecin de nivel $X$, atunci el devine turn de nivelul $X+1$ şi toate turnurile vecine de nivel X dispar, lăsând astfel locuri libere unde pot fi din nou plasate alte turnuri. Numim această operaţiune upgrade şi se va aplica de cate ori este posibil după o plasare. Dispozitivul de apărare are forma finală în momentul în care nu se mai poate plasa niciun turn.
Cunoscând configuraţia finală a dispozitivului de apărare indicaţi o succesiune minimală de plasări prin care să se ajungă în acea configuraţie.
h2. Date de intrare
Fişierul de intrare $tower8.in$ ...
Fişierul tower8.in conţine pe prima linie două numere naturale separate prin spaţiu, $N$ şi $M$ - numărul liniilor şi coloanelor dispozitivului de aparare. Pe următoarele $N$ linii se găsesc câte $M$ numere naturale nenule separate prin spaţiu – nivelele turnurilor dispozitivului de aparare în forma finală.
h2. Date de ieşire
În fişierul de ieşire $tower8.out$ ...
Fişierul tower8.out va conţine pe prima linie un număr natural $K$ reprezentând numărul minim de turnuri care au fost plasate pentru a aduce dispozitivul de aparare la forma finală. Pe următoarele $K$ linii se gasesc câte doua numere naturale $L$ şi $C$ separate prin spaţiu –cu seminficaţia: se plasează un turn de nivel $1$ pe linia $L$ , coloana $C$ a dispozitivului de aparare.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 ≤ N, M ≤ 100$
* dacă se afişează corect numai numărul minim de plasări se obţine 20% din punctaj
* dacă se afişează o succesiune corectă cu un număr mai mare de plasări se obţine 80% din punctaj cu condiţia ca numărul de plasări sa fie cel mult dublul numărului minim
* dacă se afişează corect numărul minim de plasări şi o succesiune corectă a acestora se obţine 100% din punctaj (succesiunea de plasări nu este unică!)
* **Atenţie:** poziţiile din colţurile dispozitivului de apărare au doar $3$ vecini iar celelalte de la marginea dispozitivului de apărare au doar $5$ vecini.
h2. Exemplu
table(example). |_. tower8.in |_. tower8.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2 2
1 2
3 4
| 15
1 1
1 2
1 1
2 1
1 1
1 2
1 1
2 2
1 1
1 2
1 1
2 1
1 1
1 2
1 1
|
h3. Explicaţie
...
S-a efectuat următorul şir de mutări
$|0 0| P-> |1 0| P-> |1 1| U-> |0 2| P-> |1 2| P-> |1 2| U-> |0 2| U-> |0 0| P->$
$|0 0| P-> |0 0| P-> |0 0| U-> |0 0| P-> |0 0| P-> |1 0| U-> |2 0| U-> |3 0| P->$
$|1 0| P-> |1 1| U-> |0 2| P-> |1 2| P-> |1 2| U-> |0 2| U-> |0 0| U-> |0 0| P->$
$|3 0| P-> |3 0| U-> |3 0| P-> |3 0| P-> |3 1| U-> |3 2| U-> |3 3| U-> |0 4| P->$
$|1 0| P-> |1 1| U-> |0 2| P-> |1 2| P-> |1 2| U-> |0 2| U-> |0 0| P-> |1 0| P->$
$|0 4| P-> |0 4| U-> |0 4| P-> |0 4| P-> |1 4| U-> |2 4| U-> |3 4| P-> |3 4| P->$
$|1 1| U-> |0 2| P-> |1 2|$
$|3 4| U-> |3 4| P-> |3 4|$
Unde P – semnifică faptul urmează o plasare, iar U – semnifică faptul că urmează un upgrade.
== include(page="template/taskfooter" task_id="tower8") ==
== include(page="template/taskfooter" task_id="tower8") ==
