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ţe

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 și precizări

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.

Exemplul 1

lasere.in

lasere.out

Exemplul 2

lasere.in

lasere.out

Explicație

După ce acţionează laserele terenul arată astfel:

1	1	3	4	4
8	7	6	5	4
9	3	4	6	7
0	0	-1	9	8
1	1	0	5	6

Există 6 gropi şi o tranşee. Se număra gropile chiar dacă fac parte dintr-o tranşee.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Lasere:

//Nicu Vlad Laurentiu - Liceul Teoretic "Mihail Kogalniceanu" Vaslui 100 puncte
#include <fstream>
#define N 204
#define INF 10000
#define M 10000
using namespace std;
ifstream cin("lasere.in");
ofstream cout("lasere.out");

struct laser
{
    int x,y,dir;
} X[N];
int A[N][N],n,m, i,j,k, B[M],nr=0,tr,p1,p2,s,cer;
int dx[8]={-1,-1,-1,0,1,1,1,0};
int dy[8]={-1,0,1,1,1,0,-1,-1};

int main()
{
    cin>>cer;
    cin>>n>>m;
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++) cin>>A[i][j];
    for(i=0;i<=n+1;i++) A[0][i]=A[i][0]=A[i][n+1]=A[n+1][i]=INF;

    for(k=0; k<m; k++)
    {
        cin>>X[k].x>>X[k].y>>X[k].dir;
        if(X[k].dir==1)for(i=X[k].x-1; i>=1; i--) A[i][X[k].y]--;
        else if(X[k].dir==2)for(i=X[k].y+1; i<=n; i++) A[X[k].x][i]--;
        else if(X[k].dir==3)for(i=X[k].x+1; i<=n; i++) A[i][X[k].y]--;
        else if(X[k].dir==4)for(i=X[k].y-1; i>=1; i--) A[X[k].x][i]--;
    }
     tr=0;
    for(i=1;i<=n;i++)
     {

        for(j=1;j<=n;j++)
        {
            int ok=1;
            for(int l=0;l<8 && ok;l++)
                if(A[i][j]>A[i+dx[l]][j+dy[l]])ok=0;
            if(ok==1){ B[j]=1; nr++;}

        }
        p1=0;
        for(s=1;s<n;)
            if(B[s]==1)
            {
                p1=s;
                while(B[s]) s++;
                if(s-p1>=2)tr++;
            }
            else s++;

         for(s=1;s<=n;s++){ B[s]=0;}
     }
    if(cer==1)cout<<nr<<"
";
        else cout<<tr<<"
";
   /* for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++) cout<<A[i][j]<<" ";
        cout<<"
";
    }*/
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1142 Lasere

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1142 Lasere de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1142 Lasere