Rezolvare PBinfo #2055

Pe o zonă în formă de dreptunghi cu laturile de lungimi N și M se găsesc NxM pătrate de latură 1. În centrul fiecărui pătrat se găsește înfipt câte un ac de grosime neglijabilă. Fiecare ac este descris de înălțimea sa. Această zonă se poate reprezenta ca un tablou bidimensional de dimensiuni N și M, iar fiecare element din matrice reprezintă înălțimea (număr natural nenul) fiecărui ac. În centrul pătratului (N,M) există o cameră de luat vederi de ultimă generație, mobilă, care se poate roti cu 360⁰ în orice plan, situată la nivelul solului. Dimensiunile camerei sunt neglijabile. De exemplu, dacă avem zona sub forma:

Din pătratul (4,4), în direcția N (nord), camera va obține Fig. 1, iar în direcția V (vest) va obține Fig. 2.

Pentru direcția N, camera va vedea acul de coordonatele (3,4) – în totalitate, iar acul (2,4) se va vedea doar parțial . Acul (1,4) nu se vede pentru că este acoperit total de (2,4). În direcția V, camera va vedea doar acul (4,3), deoarece (4,2) și (4,1) sunt acoperite total de (4,3). Pentru celelalte direcții se vor vedea parțial sau în totalitate acele (3,3), (3,2), (3,1), (2,3), (1,3), (2,2), (2,1), (1,2). Acul (1,1) nu se vede din cauza acului (2,2), care îl acoperă total. Acul (2,2) se vede doar parțial, pentru că o parte din el este acoperit de acul (3,3).

Cerința

1. Câte ace vede camera de luat vederi dacă se poate roti în plan vertical, doar în direcțiile N și V?
2. Câte ace vede camera de luat vederi dacă se poate roti în orice plan și în orice direcții?

Date de intrare

Fișierul de intrare ace.in conține pe prima linie numărul P care poate fi 1 sau 2, pentru prima, respectiv a doua cerință. Pe a doua linie se găsesc numerele N, M reprezentând dimensiunile tabloului, apoi pe următoarele N linii câte M numere naturale, despărțite prin câte un spațiu, reprezentând înălțimile acelor.

Date de ieșire

Fișierul de ieșire ace.out va conține pe prima linie numărul de ace văzute pentru cerință indicată de valoarea numărului P.

Restricții și precizări

• 2 ≤ N ≤ 1000
• 2 ≤ M ≤ 1000
• Elementele matricei sunt numere naturale nenule mai mici decât 1000, cu excepția numărului de pe linia N și coloana M care este 0.
• Pentru rezolvarea corectă a cerinței 1 se acordă 20 puncte, pentru rezolvarea corectă a cerinței 2 se acordă 70 de puncte, iar din oficiu se acordă 10 de puncte.
• Pentru cerința 2 există teste în valoare de 20 puncte cu N,M ≤ 50.
• Pentru cerința 2 există teste în valoare de 45 puncte cu N,M ≤ 100.

Exemplul 1:

ace.in

1
4 4
8 5 4 7
2 7 4 6
5 5 3 2
6 6 3 0

ace.out

3

Explicație

Pentru cerința 1 avem direcțiile N și V: Pentru direcția N, camera va vedea acul de coordonatele (3,4) – în totalitate, iar acul (2,4) se va vedea doar parțial. Acul (1,4) nu se va vedea pentru că este acoperit total de (2,4). În direcția V, camera va vedea doar acul (4,3), deoarece acele (4,2) și (4,1) sunt acoperite total de acul (4,3).

Exemplul 2:

ace.in

2
4 4
8 5 4 7
2 7 4 6
5 5 3 2
6 6 3 0

ace.out

11

Explicație

Pentru cerința 2 camera va vedea cele trei ace din direcțiile N și V (vezi mai sus) și opt pentru celelalte direcții se vor vedea parțial sau în totalitate acele (3,3), (3,2), (3,1), (2,3), (1,3), (2,2), (2,1), (1,2). Acul (1,1) nu se vede din cauza celui de pe (2,2) care îl acoperă total. Acul (2,2) se vede doar parțial, pentru că o parte din el este acoperit de acul (3,3).

Exemplul 3:

ace.in

2
4 3 
5 4 7
6 4 6
5 3 2
6 3 0

ace.out

8

Explicație

Pentru cerința 2 camera va vedea în N (3,3), (2,3), în V va vedea (4,2). În celelalte direcții camera va vedea parțial sau în totalitate acele (3,2), (3,1), (2,2), (1,2), (1,1).