Pagini recente » Cod sursa (job #2370910) | Cod sursa (job #2718777) | Cod sursa (job #2394712) | Cod sursa (job #2965330) | Cod sursa (job #2481241)
#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;
}