== include(page="template/taskheader" task_id="tower8") ==
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.
Poveste şi cerinţă...
h2. Date de intrare
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ă.
Fişierul de intrare $tower8.in$ ...
h2. Date de ieşire
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.
În fişierul de ieşire $tower8.out$ ...
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 |
| 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
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
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") ==
