Cod sursa(job #1598540)

Utilizator preda.andreiPreda Andrei preda.andrei Data 12 februarie 2016 23:27:02
Problema Zone Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.27 kb
#include <iostream>
#include <cstdio>

using namespace std;

long long int mat[513][513];
long long int sume[10];
bool ocupat[10];
short int pozitii[5];

bool valid(int n);
long long int suma(int x, int y, int x2, int y2);
int gasesteValid(long long int n);

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

    int n, ind, r;
    bool bunpart;

    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, "%d", &mat[i][j]);
            mat[i][j] += mat[i][j-1];
            mat[i][j] += mat[i-1][j] - mat[i-1][j-1];
        }
    }

    ind = 1;
    while(ind > 0){
        pozitii[ind]++;

        if(pozitii[ind] < n){
            if(ind == 4){
                if(valid(n)){
                    for(int i=1; i<=4; ++i)
                        fprintf(fout, "%d ", pozitii[i]);
                    return 0;
                }
            }
            else{
                if(ind == 3){
                    bunpart = true;
                    r = gasesteValid(suma(1, 1, pozitii[1], pozitii[3]));
                    if(r == 0)
                        bunpart = false;
                    else ocupat[r] = true;
                    r = gasesteValid(suma(pozitii[1]+1, 1, pozitii[2], pozitii[3]));
                    if(r == 0)
                        bunpart = false;
                    else ocupat[r] = true;
                    r = gasesteValid(suma(pozitii[2]+1, 1, n, pozitii[3]));
                    if(r == 0)
                        bunpart = false;
                    else ocupat[r] = true;

                    if(!bunpart){
                        for(int z=1; z<=9; ++z)
                            ocupat[z] = false;
                        continue;
                    }
                }
                if(ind % 2 == 1)
                    pozitii[ind + 1] = pozitii[ind];
                else pozitii[ind + 1] = 0;
                ind++;
            }
        }
        else ind--;
    }

    return 0;
}

bool valid(int n){
    short int ind;

    ind = gasesteValid(suma(1, pozitii[3]+1, pozitii[1], pozitii[4]));
    if(ind == 0)
        return false;
    ocupat[ind] = true;

    ind = gasesteValid(suma(1, pozitii[4]+1, pozitii[1], n));
    if(ind == 0)
        return false;
    ocupat[ind] = true;

    ind = gasesteValid(suma(pozitii[1]+1, pozitii[3]+1, pozitii[2], pozitii[4]));
    if(ind == 0)
        return false;
    ocupat[ind] = true;

    ind = gasesteValid(suma(pozitii[1]+1, pozitii[4]+1, pozitii[2], n));
    if(ind == 0)
        return false;
    ocupat[ind] = true;

    ind = gasesteValid(suma(pozitii[2]+1, pozitii[3]+1, n, pozitii[4]));
    if(ind == 0)
        return false;
    ocupat[ind] = true;

    ind = gasesteValid(suma(pozitii[2]+1, pozitii[4]+1, n, n));
    if(ind == 0)
        return false;
    ocupat[ind] = true;

    return true;
}

int gasesteValid(long long int n){
    for(int i=1; i<=9; ++i)
        if(n == sume[i] && !ocupat[i])
            return i;
    return 0;
}

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