== include(page="template/taskheader" task_id="mexc") ==
Proaspat scapat de conflictele sale cu politia, Gigel vrea sa organizeze o excursie la munte. El a descoperit o suprafata dreptunghiulara de N metri latime si M metri lungime, impartita in $N$ x $M$ suprafete patratice elementare de latura $1$ si cu laturile paralele cu laturile suprafetei. Pentru simplitate, ne vom referi la ea ca la o matrice notata cu $A$ avand $N$ linii (numerotate de la $1$ la $N$) si $M$ coloane (numerotate de la $1$ la $M$). Pentru fiecare patrat ( $i$ , $j$ ) se cunoaste inaltimea A(i,j) la care acesta se afla.
Dintr-un patrat ( $i$ , $j$ ), Gigel se poate deplasa, in interiorul suprafetei, in oricare din patratele: ( $i$ , $j+1$ ), ( $i$ , $j-1$ ), ( $i-1$ , $j$ ), ( $i+1$ , $j$ ), in cazul in care acestea exista. Un drum valid in viziunea lui Gigel este un drum care pleaca din orice patrat ( $x$ , $y$ )si are proprietatile:
* inaltimea fiecarui patrat ( $i$ , $j$ ) prin care trece, satisface relatia: A(i,j) >= A(x,y) - D ;(D fiind o constanta data);
* patratul ( $xf$ , $yf$ ) in care drumul se termina (denumit destinatie finala), are inaltimea mai mare sau egala cu inaltimea patratului (x,y), A(xf,yf) >= A(x,y).
h2. Cerinta
Sa se scrie un program care sa-l ajute pe Gigel sa afle, pentru fiecare patrat initial, cate destinatii finale distincte exista pentru drumurile valide care pornesc din acel patrat.
Poveste si cerinta...
h2. Date de intrare
Fisierul de intrare $mexc.in$ contine pe prima linie trei numere naturale $N$ $M$ $D$ , separate prin cate un spatiu, cu semnificatia din enunt. Fiecare dintre urmatoarele $N$ linii vor contine cate $M$ numere naturale, separate prin cate un spatiu, reprezentand valorile elementelor matricei A.
Fisierul de intrare $mexc.in$ ...
h2. Date de iesire
Fisierul de iesire $mexc.out$ va contine $N$ linii pe care se vor scrie cate $M$ numere naturale, separate prin cate un spatiu, numarul i de pe linia j din fisier reprezentand numarul de destinatii finale distincte care pot fi atinse pe drumuri valide ce pornesc din patratul (i,j), ∀ $1 ≤ i ≤ N$ , $1 ≤ j ≤ M$
h2. Restrictii
In fisierul de iesire $mexc.out$ ...
* $1 ≤ N ≤ 800$
* $1 ≤ M ≤ 800$
* $0 ≤ D ≤ 100000$
* $0 ≤ A(i,j) ≤ 100000$, ∀ $1 ≤ i ≤ N$ , $1 ≤ j ≤ M$
* Destinatia finala poate sa coincida cu punctul de plecare. Un drum format dintr-un singur patratel este considerat valid.
h2. Restrictii
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. mexc.in |_. mexc.out |
| 5 6 2
7 7 7 7 7 7
7 3 3 3 3 7
7 3 5 6 3 7
7 3 3 3 3 7
7 7 7 7 7 10
| 18 18 18 18 18 18
18 30 30 30 30 18
18 30 20 1 30 18
18 30 30 30 30 18
18 18 18 18 18 1
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicatie
Pentru patratelele de inaltime $7$ destinatia finala poate fi orice patratel de inaltime $7$ si patratelul de inaltime $10$.
Pentru patratelele de inaltime $3$ destinatia finala poate fi orice patratel.
Pentru patratelul de inaltime $5$ destinatia finala poate fi orice patratel mai putin cele de inaltime $3$.
Pentru patratelul de inaltime $6$ destinatia finala poate fi doar el insusi (nu poate trece prin patratelele de inaltime $3$ datorita primei restrictii)
Pentru patratelul de inaltime $10$ destinatia finala poate fi doar el insusi.
...
== include(page="template/taskfooter" task_id="mexc") ==
