Cod sursa(job #2482262)

Utilizator stefzahZaharia Stefan Tudor stefzah Data 27 octombrie 2019 23:07:02
Problema Zone Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("zone.in");
ofstream fout("zone.out");
int N;
int a[10], v[550][550], l1, l2, c1, c2, s[550][550];

bool Check(int x1, int y1, int x2, int y2) {
    int i;
    for (i = 1; i <= 9; i++)
        if (s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] == a[i])return true;
    return false;
}

bool Check2(int x1, int y1, int x2, int y2) {
    int i;
    bool ok = 1;
    for (i = 1; i <= 9; i++) {
        ok = 0;
        if (s[N][N] - s[x2][N] - s[N][y2] + s[x2][y2] == a[i])ok = 1;
        if (s[N][y2] - s[x2][y2] - s[N][y1] + s[x2][y1] == a[i])ok = 1;
        if (s[x2][N] - s[x1][N] - s[x2][y2] + s[x1][y2] == a[i])ok = 1;
        if (s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1] == a[i])ok = 1;

        if (s[x1][N] - s[0][N] - s[x1][y2] + s[0][y2] == a[i])ok = 1;
        if (s[x1][y2] - s[0][y2] - s[x1][y1] + s[0][y1] == a[i])ok = 1;
        if (s[x1][y1] - s[0][y1] - s[x1][0] + s[0][0] == a[i])ok = 1;

        if (s[N][y1] - s[x2][y1] - s[N][0] + s[x2][0] == a[i])ok = 1;
        if (s[x2][y1] - s[x1][y1] - s[x2][0] + s[x1][0] == a[i])ok = 1;
        if (ok == 0) {
            //cout << a[i] << " " << s[x2][y1] << "\n";
            return false;
        }
    }
    return true;
}

int main() {
    int i, j;
    fin >> N;
    for (i = 1; i <= 9; i++)
        fin >> a[i];
    for (i = 1; i <= N; i++)
        for (j = 1; j <= N; j++) {
            fin >> v[i][j];
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + v[i][j];
        }
    for (l1 = 1; l1 < N - 1; l1++)
        for (c1 = 1; c1 < N - 1; c1++) {
            if (Check(1, 1, l1, c1) == 1) {
                //cout << "*" << s[l1][c1] << endl;
                for (l2 = l1 + 1; l2 < N; l2++)
                    for (c2 = c1 + 1; c2 < N; c2++)
                        if (Check2(l1, c1, l2, c2)) {
                            fout << l1 << " " << l2 << " " << c1 << " " << c2;
                            l1 = N;
                            l2 = N;
                            c2 = N;
                            c1 = N;
                            break;
                        }
            }
        }
}