Cod sursa(job #33358)

Utilizator MariusMarius Stroe Marius Data 19 martie 2007 11:19:44
Problema Zone Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <stdio.h>

const char iname[] = "zone.in";
const char oname[] = "zone.out";

#define MAX_N 515

int N, V[11], mark[11];

int A[MAX_N][MAX_N];

int L1, C1, L2, C2, solutie;

int find(int sum) {
    for (int i = 1; i <= 9; ++ i)
	if (mark[i] == 0 && sum == V[i])
	    return i;
    return 0;
}

void print_out(int r1, int r2, int c1, int c2) {
    int indice[11];
    indice[0] = find(A[r1][N]  - A[r1][c2]);
    indice[1] = find(A[r2][c2] - A[r2][c1] - A[r1][c2] + A[r1][c1]);
    indice[2] = find(A[r2][N]  - A[r2][c2] - A[r1][N]  + A[r1][c2]);
    indice[3] = find(A[N][c1]  - A[r2][c1]);
    indice[4] = find(A[N][c2]  - A[N][c1]  - A[r2][c2] + A[r2][c1]);
    indice[5] = find(A[N][N]   - A[N][c2]  - A[r2][N]  + A[r2][c2]);
    int i;
    for (i = 0; i < 6; ++ i) {
	if (indice[i] == 0 || mark[indice[i]])
	    break ;
	mark[indice[i]] = 1;
    }
    if (i == 6)
	L1 = r1, L2 = r2, C1 = c1, C2 = c2, solutie = 1;
    else
	while (i --) mark[indice[i]] = 0;
}

void zone3(int r, int c1, int c2) {
    for (int i = r + 1; i < N; ++ i) {
	int k = find(A[i][c1] - A[r][c1]);
	if (mark[k] == 0)
	    mark[k] = 1, print_out(r, i, c1, c2), mark[k] = 0;
	if (solutie)  return ;
    }
}

void zone2(int r, int c) {
    for (int j = c + 1; j < N; ++ j) {
	int k = find(A[r][j] - A[r][c]);
	if (mark[k] == 0)
	    mark[k] = 1, zone3(r, c, j), mark[k] = 0;
	if (solutie)  return ;
    }
}

void zone1(void) {
    for (int i = 1; i < N - 1; ++ i)
	for (int j = 1; j < N - 1; ++ j) {
	    int k = find(A[i][j]);
	    if (mark[k] == 0)
		mark[k] = 1, zone2(i, j), mark[k] = 0;
	    if (solutie)  return ;
	}
}

int main(void)
{
    freopen(iname, "r", stdin);
    int i;
    int j;
    scanf("%d", & N);
    for (i = 1; i <= 9; ++ i)
	scanf("%d", V + i);
    for (i = 1; i <= N; ++ i)
	for (j = 1; j <= N; ++ j) {
	    scanf("%d", A[i] + j);
	    A[i][j] = A[i][j] + A[i - 1][j] + A[i][j - 1] - A[i - 1][j - 1];
	}
    zone1();
    freopen(oname, "w", stdout);
    printf("%d %d %d %d\n", L1, L2, C1, C2);
	if (L1 + L2 + C1 + C2 == 0)  for (;;) ;
    return 0;
}