Cod sursa(job #20691)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 21 februarie 2007 21:52:34
Problema Zone Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.77 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

const int N_MAX = 550;

int a[N_MAX][N_MAX], N;
int sm[12], st[12], aux[12], viz[12], sol[8], slin[N_MAX][N_MAX], scol[N_MAX][N_MAX];

int S, s, l1, l2, c1, c2, i, j;

void bag(int x, int y, int z, int w)
{
	sol[1] = x, sol[2] = y, sol[3] = z, sol[4] = w;
}

int back(int k)
{
	if (k == 4) {
		S = st[1] + st[2] + st[3], s = 0;

		//prima linie
		for (i = 1; i <= N; i ++) {
			s += slin[i][N];
			if (s == S) {
				l1 = i;
				break;
			}
			if (s > S) {
				return 0;
			}
		}
		if (i == N + 1) {
			return 0;
		}

		//prima coloana
		s = 0;
		for (i = 1; i <= N; i ++) {
			s += scol[l1][i];
			if (s == st[1]) {
				c1 = i;
				break;
			}
			if (s > st[1]) {
				return 0;
			}
		}
		if (i == N + 1) {
			return 0;
		}

		//a doua coloana
		s = 0;
		for (i = c1 + 1; i <= N; i ++) {
			s += scol[l1][i];
			if (s == st[2]) {
				c2 = i;
				break;
			}
			if (S > st[2]) {
				return 0;
			}
		}
		if (i == N + 1) {
			return 0;
		}

		//a doua linie
		st[7] = st[8] = st[9] = 0;
		for (i = 1; i <= N; i ++) {
			if (i <= c1) {
				st[7] += (scol[N][i] - scol[l1][i]);
				continue;
			}
			if (i <= c2) {
				st[8] += (scol[N][i] - scol[l1][i]);
				continue;
			}
			st[9] += (scol[N][i] - scol[l1][i]);
		}

		st[4] = st[5] = st[6];
		for (i = l1 + 1; i <= N; i ++) {
			l2 = i;
			st[4] += slin[i][c1];
			st[7] -= slin[i][c1];

			st[5] += (slin[i][c2] - slin[i][c1]);
			st[8] -= (slin[i][c2] - slin[i][c1]);

			st[6] += (slin[i][N] - slin[i][c2]);
			st[9] -= (slin[i][N] - slin[i][c2]);

			memcpy(aux, st, sizeof(st));

			sort(aux + 1, aux + 10);
			for (j = 1; j <= 9; j ++) {
				if (aux[j] != sm[j]) {
					break;
				}
			}
			if (j == 10) {
				if (l1 < sol[1]) {
					bag(l1, c1, l2, c2);
					continue;
				}
				if (l1 == sol[1] && c1 < sol[2]) {
					bag(l1, c1, l2, c2);
					continue;
				}
				if (l1 == sol[1] && c1 == sol[2] && l2 < sol[3]) {
					bag(l1, c2, l2, c2);
					continue;
				}
				if (l1 == sol[1] && c1 == sol[2] && l2 == sol[3] && c2 < sol[4]) {
					bag(l1, c2, l2, c2);
					continue;
				}
			}
		}
		
	} else {
		for (int c = 1; c <= 9; c ++) {
			if (!viz[c]) {
				st[k] = sm[c];
				viz[c] = 1;
				if (back(k + 1) > 20) return 1;
				viz[c] = 0;
			}
		}
	}
	return 1;
}

int main()
{
	freopen("zone.in", "r", stdin);
	freopen("zone.out", "w", stdout);

	scanf("%d\n", &N);
	for (i = 1; i <= 9; i ++) {
		scanf("%d ", &sm[i]);
	}
	sort(sm + 1, sm + 10);
	
	for (i = 1; i <= N; i ++) {
		for (j = 1; j <= N; j ++) {
			scanf("%d ", &a[i][j]);
			slin[i][j] = slin[i][j - 1] + a[i][j];
			scol[i][j] = scol[i - 1][j] + a[i][j];
		}
	}
	sol[1] = sol[2] = sol[3] = sol[4] = 1000;

	int bla = back(1);
	if (bla > 20) {
		printf("banana strikes again");
	}
	printf("%d %d %d %d\n", sol[1], sol[3], sol[2], sol[4]);
	
	return 0;
}