Editing 2902 - Pavaj


= 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>