== 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:
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).
* 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.
h2. Date de intrare
Fisierul de intrare $mexc.in$ ...
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.
h2. Date de iesire
In fisierul de iesire $mexc.out$ ...
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
* $... ≤ ... ≤ ...$
* $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. Exemplu
table(example). |_. mexc.in |_. mexc.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 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
|
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") ==
