Question

Cerința --> #565 Acoperire pbinfo (ajutor am nevoie de 100 pct.)

Gigel deține un teren de formă dreptunghiulară, împărțite în n•m sectoare, dispuse pe n linii și m coloane. În anumite sectoare sunt instalate camere de luat vederi. Fiecare cameră acoperă anumite sectoare ale terenului, pe diagonală și are o anumită putere k reprezentând numărul de sectoare pe care le acoperă pe fiecare din cele 4 direcții, inclusiv sectorul în care se află camera.

În figura de mai jos sunt afișate sectoarele acoperite de o cameră de putere 3.



Determinați câte sectoare ale terenului nu sunt acoperite de nici o cameră.

Date de intrare
Programul citește de la tastatură numerele n m k, reprezentând dimensiunile terenului și numărul de camere, apoi k triplete i j p, reprezentând coordonatele fiecărei camere șî puterea ei.

Date de ieșire
Programul va afișa pe ecran numărul C, reprezentând numărul de sectoare neacoperite.

Restricții și precizări
1 ≤ n , m ≤ 1000
1 ≤ p ≤ 1000
1 ≤ i ≤ n
1 ≤ j ≤ m
1 ≤ p ≤ min(n,m)
o cameră poate acoperi un sector în care se află o altă cameră



Exemplu
Intrare:
5 7 4
1 7 2
2 3 3
4 2 3
4 5 4

Ieșire:
16

Answer 1

#include <bits/stdc++.h>

using namespace std;

int n,m,k,i,j,p;

int main()
{

    cin >> n >> m >> k;

    int a[n+1][m+1]; 

    for(int x=1;x<=n;x++) //Creeam o matrice complet din zerouri
        for(int y=1;y<=m;y++)
            a[x][y]=0;

    for(int x=1;x<=k;x++)
        cin >> i >> j >> p, a[i][j]=p; //Punem camerele

    for(int y=1;y<=n;y++)
    {
        for(int x=1;x<=m;x++)
            if(a[y][x]!=0 and a[y][x]!=-1) //Controlam daca am dat de o camera
            {
                int k=1;
                while(k<=a[y][x]-1) //Cream un while care va repeta structura de p-1(a[y][x]-1) ori
                {
                    if(y+k<=n and x+k<=m and a[y+k][x+k]==0) a[y+k][x+k]=-1; //Controlam daca nu iesim din matrice si daca nu dam de o camera!!! Daca nu punem -1
                    if(y+k<=n and x-k>=1 and a[y+k][x-k]==0) a[y+k][x-k]=-1;
                    if(y-k>=1 and x+k<=m and a[y-k][x+k]==0) a[y-k][x+k]=-1;
                    if(y-k>=1 and x-k>=1 and a[y-k][x-k]==0) a[y-k][x-k]=-1;
                    k++;
                }
            }
    }

    int S=0;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a[i][j]==0) S++; //Controlam cite zone cu 0 au ramas

    cout << S; //Afisam

    return 0;

}