Cod sursa(job #1163865)

Utilizator horatiu13Horatiu horatiu13 Data 1 aprilie 2014 17:48:30
Problema Zone Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 kb
#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;
}