Fişierul intrare/ieşire:	mexc.in, mexc.out	Sursă	ONI 2008 - baraj
Autor	Adrian Diaconu	Adăugată de	Pripoae Teodor Anton •toni2007
Timp execuţie pe test	0.35 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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).

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.

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.

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

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.

Exemplu

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.

Cum se trimit solutii?