Cod sursa(job #33348)

Utilizator MariusMarius Stroe Marius Data 19 martie 2007 10:49:58
Problema Zone Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <stdio.h>
#include <stdlib.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;

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) {
	freopen(oname, "w", stdout);
	printf("%d %d %d %d\n", r1, r2, c1, c2);
	exit(0);
    } else {
	for (i = 0; i < 6; ++ 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;
    }
}

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;
    }
}

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;
	}
}

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();
    return 0;
}