Cod sursa(job #1698614)

Utilizator preda.andreiPreda Andrei preda.andrei Data 4 mai 2016 21:22:24
Problema Zone Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.83 kb
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long int lli;

lli mat[513][513];
lli sume[10];
bool folosit[10];

int l1, c1, l2, c2;
bool gasit = false;

int sumaValabila(lli sum);
lli suma(int x1, int y1, int x2, int y2);
void backtracking(int &i1, int &j1, int &i2, int &j2, int n, int zona);

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 - 1][j - 1] + mat[i][j - 1];
        }
    }

    int a, b, c, d;
    backtracking(a, b, c, d, n, 0);

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

void backtracking(int &i1, int &j1, int &i2, int &j2, int n, int zona){
    int poz;
    //cout << zona << "\n";
    //cout << i1 << " " << j1 << " " << i1 << " " << j2 << "\n";
    switch(zona){
    case 0:
        for(i1 = 1; i1 < n - 1 && !gasit; ++i1){
            backtracking(i1, j1, i2, j2, n, zona + 1);
        }
        break;
    case 1:
        for(j1 = 1; j1 < n - 1 && !gasit; ++j1){
            poz = sumaValabila(suma(1,1, i1, j1));
            if(poz == 0)
                continue;

            folosit[poz] = true;
            backtracking(i1, j1, i2, j2, n, zona + 1);
            folosit[poz] = false;
        }
        break;
    case 2:
        for(j2 = j1 + 1; j2 < n && !gasit; ++j2){
            poz = sumaValabila(suma(1, j1 + 1, i1, j2));
            if(poz == 0)
                continue;

            folosit[poz] = true;
            backtracking(i1, j1, i2, j2, n, zona + 1);
            folosit[poz] = false;
        }
        break;
    case 3:
        poz = sumaValabila(suma(1, j2 + 1, i1, n));
        if(poz == 0)
            return;
        folosit[poz] = true;
        backtracking(i1, j1, i2, j2, n, zona + 1);
        break;
    case 4:
        for(i2 = i1 + 1; i2 < n; ++i2){
            poz = sumaValabila(suma(i1 + 1, 1, i2, j1));
            if(poz == 0)
                continue;

            folosit[poz] = true;
            backtracking(i1, j1, i2, j2, n, zona + 1);
            folosit[poz] = false;
        }
        break;
    case 5:
        poz = sumaValabila(suma(i1 + 1, j1 + 1, i2, j2));
        if(poz == 0)
            return;
        folosit[poz] = true;
        backtracking(i1, j1, i2, j2, n, zona + 1);
        folosit[poz] = false;
        break;
    case 6:
        poz = sumaValabila(suma(i1 + 1, j2 + 1, i2, n));
        if(poz == 0)
            return;
        folosit[poz] = true;
        backtracking(i1, j1, i2, j2, n, zona + 1);
        folosit[poz] = false;
        break;
    case 7:
        poz = sumaValabila(suma(i2 + 1, 1, n, j1));
        if(poz == 0)
            return;
        folosit[poz] = true;
        backtracking(i1, j1, i2, j2, n, zona + 1);
        folosit[poz] = false;
        break;
    case 8:
        poz = sumaValabila(suma(i2 + 1, j1 + 1, n, j2));
        if(poz == 0)
            return;
        folosit[poz] = true;
        backtracking(i1, j1, i2, j2, n, zona + 1);
        folosit[poz] = false;
        break;
    case 9:
        poz = sumaValabila(suma(i2 + 1, j2 + 1, n, n));
        if(poz == 0)
            return;
        gasit = true;
        l1 = i1;
        l2 = i2;
        c1 = j1;
        c2 = j2;
        break;
    }
}

int sumaValabila(lli sum){
    for(int i = 1; i <= 10; ++i){
        if(sume[i] == sum && !folosit[i])
            return i;
    }
    return 0;
}

lli 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];
}