Fișierul intrare/ieșire	lasere.in, lasere.out	Sursă	OJI 2015 clasa a 7-a
Autor	Vlad-Laurențiu Nicu	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.2 sec	Limită de memorie	8192 KB
Scorul tău	N/A	Dificultate	1

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Lasere (clasa a 7-a)

Se consideră un teren reprezentat printr-o matrice cu n linii și n coloane având elemente numere naturale. În fiecare element al matricei este memorată înălțimea zonei de teren corespunzătoare ca poziție elementului respectiv. Pe acest teren sunt amplasate m lasere, în poziții cunoscute. Un laser este îndreptat spre unul dintre cele 4 puncte cardinale, codificate prin numere astfel: Nord prin valoarea 1, Est prin valoarea 2, Sud prin valoarea 3 și respectiv Vest prin valoarea 4. Fiecare laser va executa o singură tragere și ca urmare va scădea cu 1 valorile tuturor elementelor din matrice din direcția sa de tragere, exceptând poziția laserului respectiv.

După efectuarea tuturor tragerilor, se caută pozițiile tuturor gropilor și ale tranșeelor. Numim groapă un element din matrice pentru care toate cele 8 elemente învecinate pe linie, coloană sau diagonale au valori mai mari sau egale decât el. Numim tranșee o secvență maximală formată din două sau mai multe gropi situate pe aceeași linie, pe coloane consecutive. Secvența se numește maximală dacă nu mai poate fi prelungită la niciunul dintre capete.

Cerință

Cunoscând configurația terenului și amplasarea laserelor, să se rezolve una dintre următoarele două cerințe:

1. să se determine numărul de gropi din teren, după executarea tragerilor;
2. să se determine numărul de tranșee existente, după executarea tragerilor.

Date de intrare

Fișierul de intrare lasere.in conține pe prima linie un număr natural c care reprezintă cerința ce urmează să fie rezolvată (1 sau 2). Pe a doua linie se află două numere naturale n și m, reprezentând numărul de linii și de coloane ale matricei, respectiv numărul de lasere. Pe următoarele n linii se află câte n numere naturale, reprezentând elementele matricei. Pe următoarele m linii sunt descrise cele m lasere, câte un laser pe o linie. Pe o linie care descrie un laser se află 3 numere naturale i j d, cu semnificația că se află un laser pe linia i și coloana j (1 ≤ i, j ≤ n), care trage în direcția d (1 ≤ d ≤ 4). Valorile situate pe aceeași linie sunt separate prin spațiu.

Date de ieșire

Fișierul de ieșire lasere.out va conține pe prima linie un singur număr natural. Acest număr reprezintă numărul de gropi (dacă c = 1) sau numărul de tranșee (dacă c = 2).

Restricții

• 4 ≤ n ≤ 200
• 1 ≤ m ≤ 200
• Numerotarea liniilor și a coloanelor este de la 1 la n.
• Elementele matricei din fișierul de intrare sunt numere naturale de maxim 4 cifre.
• Pozițiile laserelor sunt distincte.
• Pentru teste valorând 30% din punctaj cerința este 1.

Exemplu