# PBinfo #604 – maria – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: andrei

## Enunț

Cerința
Maria dansează! Lecțiile de dans se desfășoară într-o sală imensă, împărțită în n*m sectoare pătratice cu dimensiunea 1, dispuse pe n linii și m coloane. În anumite sectoare se află diverse obstacole, astfel că acele sectoare nu pot fi utilizate pentru dans. Maria are nevoie pentru dans de o zonă dreptunghiulară de dimensiuni p, q, cu laturile paralele cu pereții sălii, care să nu conțină obstacole și vrea ca în fiecare zi să danseze într-o zonă diferită de cele în care a dansat deja. Determinați numărul de zile în care Maria poate dansa așa cum își dorește.

Date de intrare
Fișierul de intrare maria.in conține pe prima linie numerele n m p q. A doua linie conține numărul k de sectoare din sală în care se află obstacole. Fiecare dintre următoarele k linii conține două numere i j, reprezentând linia și coloana unui sector ce conține un obstacol.

Date de ieșire
Fișierul de ieșire maria.out va conține pe prima linie numărul Z de zile în care Maria poate dansa în zone diferite.

Restricții și precizări

1 ≤ n, m, p, q ≤ 1000
0 ≤ k ≤ 1000
1 ≤ i ≤ n, 1 ≤ j ≤ m
două zone de dans sunt distincte dacă diferă prin cel puțin un sector
zona de dans poate fi orientată astfel încât să ocupe p linii și q coloane sau q linii și p coloane

Exemplu:
maria.in

5 6 2 3
3
2 2
3 5
4 3
maria.out

5
Explicație
Cele 5 moduri de stabilire a zonei de dans sunt:

## Cod sursă C++

```cpp
#include <fstream>
using namespace std;
ifstream in("maria.in");
ofstream out("maria.out");
int mat[1001][1001], S[1001][1001];
int n, m, p, q, k, rez = 0;
int main() {
    in  >> n >> m >> p >> q >> k;
    for (int i = 1; i <= k; ++i) {
        int lin, col;
        in >> lin >> col;
        mat[lin][col] = 1;
    } for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + mat[i][j];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            int lin, col;
            lin = i + p - 1;
        	col = j + q - 1;
            if (lin <= n && col <= m)
                if (S[lin][col] - S[lin][j - 1] - S[i - 1][col] + S[i - 1][j - 1] == 0)
                    rez++;
            lin = i + q - 1;
        	col = j + p - 1;
            if (lin <= n && col <= m)
                if (S[lin][col] - S[lin][j - 1] - S[i - 1][col] + S[i - 1][j - 1] == 0)
                    rez++;
        } out << rez;
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/604)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/604/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-604/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)