Cod sursa(job #1698596)

Utilizator preda.andreiPreda Andrei preda.andrei Data 4 mai 2016 20:47:03
Problema Zone Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.81 kb
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long int lli;

lli mat[513][513];

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

void solutie(int n, int &l1, int &c1, int &l2, int &c2);
void sortare(lli v[], int n);
int sumaValabila(lli sum);
lli suma(int x1, int y1, int x2, int y2);
bool combinatieValida(int l1, int c1, int l2, int c2, int n, int ind);

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

    int n, l1, l2, c1, c2;

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

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

    solutie(n, l1, c1, l2, c2);

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

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

bool combinatieValida(int l1, int c1, int l2, int c2, int n, int ind){
    int poz;
    switch(ind){
        case 1: return sumaValabila(suma(l2 + 1, c2 + 1, n, n));  break;
        case 2: poz = sumaValabila(suma(l2 + 1, c1 + 1, n, c2));  break;
        case 3: poz = sumaValabila(suma(l2 + 1, 1, n, c1));       break;
        case 4: poz = sumaValabila(suma(l1 + 1, c2 + 1, l2, n));  break;
        case 5: poz = sumaValabila(suma(l1 + 1, c1 + 1, l2, c2)); break;
        case 6: poz = sumaValabila(suma(l1 + 1, 1, l2, c1));      break;
        default : return false; break;
    }

    if(poz == 0)
        return false;

    folosit[poz] = true;

    bool rez = combinatieValida(l1, c1, l2, c2, n, ind - 1);

    folosit[poz] = false;

    return rez;
}

void solutie(int n, int &l1, int &c1, int &l2, int &c2){
    for(int i1 = 1; i1 < n; ++i1){
        for(int j1 = 1; j1 < n; ++j1){
            int poz = sumaValabila(suma(1, 1, i1, j1));

            if(poz == 0)
                continue;

            folosit[poz] = true;

            for(int j2 = j1 + 1; j2 <= n; ++j2){
                int poz2 = sumaValabila(suma(1, j1 + 1, i1, j2));

//                cout << i1 << " " << j1 << " " << j2 << "\n";
//                cout << suma(1, j1 + 1, i1, j2) << "\n";
//                for(int z = 1; z <= 9; ++z){
//                    cout << sume[z] << " " << folosit[z] << "\n";
//                }
//                cin.get();

                if(poz2 != 0){
                    folosit[poz2] = true;

                    int poz3 = sumaValabila(suma(1, j2 + 1, i1, n));
                    if(poz3 != 0){
                        folosit[poz3] = true;

                        for(int i2 = i1 + 1; i2 <= n; ++i2){
                            if(combinatieValida(i1, j1, i2, j2, n, 6)){
                                l1 = i1;
                                c1 = j1;
                                l2 = i2;
                                c2 = j2;
                                return;
                            }
                        }

                        folosit[poz3] = false;
                    }

                    folosit[poz2] = false;
                }
            }

            folosit[poz] = false;
        }
    }
}

void sortare(lli v[], int n){
    for(int i = 1; i < n; ++i){
        int x = i;
        for(int j = i + 1; j <= n; ++j){
            if(v[j] < v[x])
                x = j;
        }

        if(x != i){
            int aux = v[i];
            v[i] = v[x];
            v[x] = aux;
        }
    }
}

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