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

maria.out

Explicație

Cele 5 moduri de stabilire a zonei de dans sunt:

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 Maria:

//maria

#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("maria.in");
ofstream fout("maria.out");

int a[1005][1005], n, m , p , q, s[1005][1005];

int main(){
    int k;
    fin  >> n >> m >> p >> q >> k;
    for(int pp = 1 ; pp <= k ; ++pp)
    {
        int i ,j ;
        fin >> i >> j;
        a[i][j] = 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] + a[i][j];
    int Z = 0;
    for(int i =1 ; i <= n ;++ i)
        for(int j =1  ; j <= m ; ++j)
        {
            int x,y;
            x = i + p - 1, y = j + q - 1;
            if(x <= n && y <= m)
                if(s[x][y] - s[x][j-1] - s[i-1][y] + s[i-1][j-1] == 0)
                    Z ++; // cout << i << " " << j << " p q
";
            x = i + q - 1, y = j + p - 1;
            if(x <= n && y <= m)
                if(s[x][y] - s[x][j-1] - s[i-1][y] + s[i-1][j-1] == 0)
                    Z ++; // cout << i << " " << j << " q p
";
        }
    fout << Z;
    return 0;
}

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 #604 Maria

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #604 Maria 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 #604 Maria