Raul: Pagină nouă: = Cerința = Curtea bunicului are forma unei matrice cu `n` linii și `m` coloane și este pavată cu `n*m` dale, o parte dintre acestea fiind deteriorate. Bunicul a realizat un plan al curții în care a marcat cu `0` dalele deteriorate și cu `1` pe cele nedeteriorate. Bunicul a primit `k` oferte pentru a vinde zone dreptunghiulare ale curții. Fiecare zonă este determinată de coordonatele `l1 c1 l2...`


2023-12-15T18:19:32Z
Pagină nouă:  = Cerința = Curtea bunicului are forma unei matrice cu <code>n</code> linii și <code>m</code> coloane și este pavată cu <code>n*m</code> dale, o parte dintre acestea fiind deteriorate. Bunicul a realizat un plan al curții în care a marcat cu <code>0</code> dalele deteriorate și cu <code>1</code> pe cele nedeteriorate.  Bunicul a primit <code>k</code> oferte pentru a vinde zone dreptunghiulare ale curții. Fiecare zonă este determinată de coordonatele <code>l1 c1 l2...
New page


= Cerința =

Curtea bunicului are forma unei matrice cu <code>n</code> linii și <code>m</code> coloane și este pavată cu <code>n*m</code> dale, o parte dintre acestea fiind deteriorate. Bunicul a realizat un plan al curții în care a marcat cu <code>0</code> dalele deteriorate și cu <code>1</code> pe cele nedeteriorate.



Bunicul a primit <code>k</code> oferte pentru a vinde zone dreptunghiulare ale curții. Fiecare zonă este determinată de coordonatele <code>l1 c1 l2 c2</code> a două colțuri opuse ale ei. Pentru fiecare zonă bunicul dorește să afle dacă conține doar dale nedeteriorate, doar dale deteriorate sau conține și dale deteriorate și dale nedeteriorate.



= Date de intrare =

Fișierul de intrare <code>pavaj.in</code> conține pe prima linie numerele <code>n m k</code>. Următoarele <code>n</code> linii conțin câte <code>m</code> valori <code>0</code> sau <code>1</code>, reprezentând planul curții. Următoarele <code>k</code> linii conțin câte patru valori, <code>l1 c1 l2 c2</code>, reprezentând coordonatele a două colțuri opuse ale unei zone.



= Date de ieșire =

Fișierul de ieșire <code>pavaj.out</code> va conține <code>k</code> linii. Fiecare linie va conține valoarea <code>0</code>, <code>1</code> sau <code>2</code>, după cum zona corespunzătoare din fișierul de intrare:



* conține doar dale deteriorate

* conține doar dale nedeteriorate

* conține atât dale nedeteriorate, cât și dale deteriorate



= Restricții și precizări =



* <code>1 ≤ n, m ≤ 1000</code>

* <code>1 ≤ k ≤ 100000</code>

* <code>1 ≤ l1, l2 ≤ n</code>

* <code>1 ≤ c1, c2 ≤ m</code>

* numerotarea liniilor și a coloanelor începe de la <code>1</code>

* pentru 50% din teste <code>1 ≤ n, m, k ≤ 1000</code>



= Exemplu: =

<code>pavaj.in</code>

 4 6 3

 0 0 1 1 1 0

 0 0 1 1 1 0

 0 0 0 0 0 1

 1 0 1 0 1 0

 1 1 3 2

 2 4 1 5

 1 6 4 2

<code>pavaj.out</code>

 0

 1

 2



== Încărcare soluție ==



=== Lipește codul aici ===

<syntaxhighlight lang="python" line="1">

#include <iostream>

#include <fstream>

using namespace std;



int main()

{

    ifstream cin("pavaj.in");

    ofstream cout("pavaj.out");

    int n, m, t, s[1001][1001], i1, j1, i2, j2;

    cin >> n >> m >> t;

    for (int i = 1; i <= n; i++)

        for (int j = 1; j <= m; j++)

            cin >> s[i][j];

    for (int i = 1; i <= n; ++i)

        for (int j = 1; j <= m; ++j)

            s[i][j] = s[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

    for (int i = 1; i <= t; i++)

    {

        cin >> i1 >> j1 >> i2 >> j2;

        int sum = 0, nr = 0;

        if (i1 <= i2 && j1 <= j2)

            sum = s[i2][j2] - s[i1 - 1][j2] - s[i2][j1 - 1] + s[i1 - 1][j1 - 1], nr = (j2 - j1 + 1) * (i2 - i1 + 1);

        else if (i1 >= i2 && j1 <= j2)

            sum = s[i1][j2] - s[i2 - 1][j2] - s[i1][j1 - 1] + s[i2 - 1][j1 - 1], nr = (i1 - i2 + 1) * (j2 - j1 + 1);

        else if (i1 <= i2 && j1 >= j2)

            sum = s[i2][j1] - s[i1 - 1][j1] - s[i2][j2 - 1] + s[i1 - 1][j2 - 1], nr = (i2 - i1 + 1) * (j1 - j2 + 1);

        else

            sum = s[i1][j1] - s[i2 - 1][j1] - s[i1][j2 - 1] + s[i2 - 1][j2 - 1], nr = (i1 - i2 + 1) * (j1 - j2 + 1);

        if (sum == 0)

            cout << 0 << '\n';

        else if (sum == nr)

            cout << 1 << '\n';

        else

            cout << 2 << '\n';

    }

}





</syntaxhighlight>

2902 - Pavaj - Revision history