Cod sursa(job #2481241)

Utilizator mirunazMiruna Zavelca mirunaz Data 26 octombrie 2019 17:27:55
Problema Zone Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.5 kb
#include <fstream>
using namespace std;
ifstream in("zone.in");
ofstream out("zone.out");
#define N 513
#define M 9
int a[N][N], v[M], zona[M];
pair<int, int> c, l, cf = {N, N}, lf = {N, N};
bool viz[M];

void verif_lin(int n) {
    int sum1 = zona[0] + zona[1] + zona[2];
    int sum2 = zona[3] + zona[4] + zona[5];
    int sum3 = zona[6] + zona[7] + zona[8];
    int sum4 = zona[0] + zona[3] + zona[6];
    int sum5 = zona[1] + zona[4] + zona[7];
    int sum6 = zona[2] + zona[5] + zona[8];
    l = {M, M}, c = {M, M};

    for(int i = 1; i < n; i ++) {   // l1 minim posibil
        if (a[i][n] == sum1) {
            for (int k = 1; k < n; k ++) {  // c1 minim posibil
                if (a[n][k] == sum4) {
                    for (int j = i + 1; j <= n; j ++) { // l2 minim posibil
                        if (a[j][n] - a[i][n] == sum2 &&
                            a[n][n] - a[j][n] == sum3) {
                            for (int h = k + 1; h <= n; h ++) { // c2 minim posibila
                                if (a[n][h] - a[n][k] == sum5 &&
                                    a[n][n] - a[n][h] == sum6) {
                                    l.first = i;    l.second = j;
                                    c.first = k;    c.second = h;
                                    return ;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

void bkt(int p, int n) {
    if (p == M) {
        verif_lin(n);
        if (l.first < lf.first) {
            lf = l; cf = c;
        } else if (l.first == lf.first) {
            if (c.first < cf.first) {
                lf = l; cf = c;
            } else if (c.first == cf.first) {
                if (l.second < lf.second) {
                    lf = l; cf = c;
                } else if (c.second < cf.second) {
                    lf = l; cf = c;
                }
            }
        }
        return ;
    }
    for (int i = 0; i < M; i ++) {
        if (viz[i] == 0) {
            zona[p] = v[i];
            viz[i] = true;
            bkt(p + 1, n);
            viz[i] = false;
        }
    }
}

int main() {
    int n;
    in >> n;
    for (int i = 0; i < M; i ++) {
        in >> v[i];
    }

    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            in >> a[i][j];
            a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
        }
    }

    bkt(0, n);
    out << lf.first << ' ' << lf.second << ' ' << cf.first << ' ' << cf.second;
    return 0;
}