Pagini recente » Cod sursa (job #2319369) | Cod sursa (job #1127298) | Cod sursa (job #599926) | Cod sursa (job #519379) | Cod sursa (job #1163865)
#include <cstdio>
#define Nmax 515
using namespace std;
FILE *fi = fopen("zone.in", "r");
FILE *fo = fopen("zone.out", "w");
int a[Nmax][Nmax];
int b[Nmax][Nmax];
int v[10];
int s[10];
int n;
int l1, l2;
int c1, c2;
int sem = 1;
void scmb(int &X, int &Y)
{
int aux = X;
X = Y;
Y = aux;
}
int parcurgere(int V[], int st, int dr)
{
int di = 1;
int dj = 0;
while (st <= dr)
{
if (V[st] > V[dr])
{
scmb(V[st], V[dr]);
scmb(di, dj);
}
st += di;
dr -= dj;
}
return st;
}
void qsort(int V[], int st, int dr)
{
for (int i = 1; i<dr; i++)
for (int j = i+1; j<=dr; j++)
if (V[i] > V[j])
scmb(V[i], V[j]);
/*
while (st <= dr)
{
int poz = parcurgere(V, st, dr);
qsort(V, st, poz-1);
qsort(V, poz+1, dr);
}
*/
}
void citire()
{
fscanf(fi, "%d", &n);
for (int i = 1; i<=9; i++) fscanf(fi, "%d", &v[i]);
qsort(v, 1, 9);
for (int i = 1; i<=n; i++)
for (int j = 1; j<=n;j++)
{
fscanf(fi, "%d", &a[i][j]);
b[i][j] = b[i-1][j] + b[i][j-1] - b[i-1][j-1] + a[i][j];
}
/*
for (int i = 1; i<=n; i++)
{
for (int j = 1; j<=n; j++)
printf("%3d ", b[i][j]);
printf("\n");
}*/
}
int verificare()
{
s[1] = b[l1][c1];
s[2] = b[l1][c2] - s[1];
s[3] = b[l1][n] - b[l1][c2];
s[4] = b[l2][c1] - s[1];
s[5] = b[l2][c2] - b[l1][c2] - b[l2][c1] + s[1];
s[6] = b[l2][n] - b[l2][c2] - b[l1][n] + b[l1][c2];
s[7] = b[n][c1] - b[l2][c1];
s[8] = b[n][c2] - b[n][c1] - b[l2][c2] + b[l2][c1];
s[9] = b[n][n] - b[n][c2] - b[l2][n] + b[l2][c2];
qsort(s, 1, 9);
for (int i = 1; i<=9; i++)
if (v[i] != s[i])
return 0;
return 1;
}
void bt(int k)
{
if (sem)
if (k == 1 && sem) // l1
{
for (int i = 1; i<n && sem; i++)
{
l1 = i;
bt (k+1);
}
}
else if (k == 2 && sem) // c1
{
for (int i = 1; i<n && sem; i++)
{
c1 = i;
bt(k+1);
}
}
else if (k == 3 && sem) // l2
{
for (int i = l1+1; i<=n && sem; i++)
{
l2 = i;
bt(k+1);
}
}
else if (k == 4 && sem) // c2
{
for (int i = c1+1; i<=n && sem; i++)
{
c2 = i;
if (verificare())
sem = 0;
}
}
}
int main()
{
citire();
bt(1);
fprintf(fo, "%d %d %d %d\n", l1, l2, c1, c2);
return 0;
}