Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | tower8.in, tower8.out | Sursă | Lot Baia Mare 2013 - Baraj 1 Seniori |
| Autor | Adrian Panaete | Adăugată de |  Daniel Constantin Anghel •Magnvs |
| Timp execuţie pe test | 1.75 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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.
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ă.
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.
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.
Exemplu
| 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 |
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 ↦ 0 0 ↦ 0 0 ↦ 0 0 ↦ 0 0 ↦ 1 0 ↦ 2 0 ↦ 3 0 ↦
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 ↦ 3 0 ↦ 3 0 ↦ 3 0 ↦ 3 1 ↦ 3 2 ↦ 3 3 ↦ 0 4 ↦
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 ↦ 0 4 ↦ 0 4 ↦ 0 4 ↦ 1 4 ↦ 2 4 ↦ 3 4 ↦ 3 4 ↦
1 1 U 0 2 P 1 2
3 4 ↦ 3 4 ↦ 3 4
Unde P – semnifică faptul urmează o plasare în poziţia haşurată iar U – semnifică faptul că urmează un upgrade în pozitia bordată cu ajutorul turnului subliniat din poziţie vecină.
