Cod sursa(job #1732044)

Utilizator preda.andreiPreda Andrei preda.andrei Data 20 iulie 2016 17:04:51
Problema Zone Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <cstdio>

using namespace std;

#define NMAX 513

long long sume[10];
bool folosit[10];
long long mat[NMAX][NMAX];

void aflaCoordonate(int n, int &l1, int &c1, int &l2, int &c2);
void sterge(long long s);
bool marcheaza(long long s);
long long suma(int x1, int y1, int x2, int y2);

int main()
{
    FILE *fin = fopen("zone.in", "r");
    FILE *fout = fopen("zone.out", "w");

    int n;
    fscanf(fin, "%d", &n);

    for (int i = 1; i <= 9; ++i) {
        fscanf(fin, "%lld", &sume[i]);
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            fscanf(fin, "%lld", &mat[i][j]);
            mat[i][j] += mat[i - 1][j] + mat[i][j - 1] - mat[i - 1][j - 1];
        }
    }

    int l1, c1, l2, c2;
    aflaCoordonate(n, l1, c1, l2, c2);

    fprintf(fout, "%d %d %d %d", l1, l2, c1 - 1, c2 - 1);
    return 0;
}

void aflaCoordonate(int n, int &l1, int &c1, int &l2, int &c2)
{
    for (l1 = 1; l1 < n; ++l1) {
        for (c1 = 2; c1 < n; ++c1) {
            if (marcheaza(suma(1, 1, l1, c1 - 1))) {

                for (l2 = l1 + 1; l2 <= n; ++l2) {
                    if (marcheaza(suma(l1 + 1, 1, l2, c1 - 1))) {

                        if (marcheaza(suma(l2 + 1, 1, n, c1 - 1))) {
                            for (c2 = c1 + 1; c2 <= n; ++c2) {
                                if (marcheaza(suma(l1 + 1, c1, l2, c2 - 1))) {
                                    return;
                                }
                            }

                            sterge(suma(l2 + 1, 1, n, c1 - 1));
                        }

                        sterge(suma(l1, 1, l2 - 1, c1 - 1));
                    }
                }

                sterge(suma(1, 1, l1 - 1, c1 - 1));
            }
        }
    }
}

void sterge(long long s)
{
    for (int i = 1; i <= 9; ++i) {
        if (sume[i] == s && folosit[i]) {
            folosit[i] = false;
            return;
        }
    }
}

bool marcheaza(long long s)
{
    for (int i = 1; i <= 9; ++i)
        if (sume[i] == s && !folosit[i])
            return folosit[i] = true;
    return false;
}

long long suma(int x1, int y1, int x2, int y2)
{
    return mat[x2][y2] - mat[x2][y1 - 1] - mat[x1 - 1][y2] + mat[x1 - 1][y1 - 1];
}