Cod sursa(job #542563)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 26 februarie 2011 14:59:19
Problema Pixels Scor 0
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 1.67 kb
#include <cstdio>
#include <cstring>
#include <string>
#define maxn 20
using namespace std;
int N, c[maxn][maxn][5], A[maxn][maxn], B[maxn][maxn], sol[maxn][maxn], res;

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int viz[maxn][maxn];
void check ()
{	
	int cant = 0, cost = 0;
	int i, j, k, x, y;
	memset (viz, 0, sizeof (viz));
	for (i = 1; i <= N; i++)
		for (j = 1; j <= N; j++)
		{
			viz[i][j] = 1;
			for (k = 0; k < 4; k++)
			{
				x = i + dx[k];
				y = j + dy[k];
				if (x < 1 || x > N || y < 1 || y > N) continue;
				if (viz[x][y] == 0) {
					if (sol[x][y] == 1)
						cant += A[x][y] ;else	cant+= B[x][y];}
				if (viz[x][y] == 0 && sol[x][y] != sol[i][j])
					cost += c[x][y][k];
			}
		}
/*	for (i = 1; i <= N; i++) {
		for (j = 1; j <= N; j++)
			printf ("%d ", sol[i][j]);
		printf ("\n");
	}
	printf ("%d %d\n", cant, cost);*/
	res = max (res, cant - cost);
}
int nr;
void fill (int x, int y)
{	
	int i;
	if (x < 1 || x > N || y < 1 || y > N) return;
	
	//if (sol[x][y]) return;
	
	if (nr == N * N) {check ();return ;}
	if (sol[x][y]) return ;
	for (i = 1; i <= 2; i++) {
		sol[x][y] = i;
		
		nr++;	
		fill (x - 1, y);
	
		fill (x, y + 1);
		
		fill (x + 1, y);
		
		fill (x, y - 1);
		sol[x][y] = 0;
		nr--;
	}
}
int main ()
{


	freopen ("pixels.in", "r", stdin);
	freopen ("pixels.out", "w", stdout);

	int i, j;
	scanf ("%d\n", &N);
	for (i = 1; i <= N; i++)
		for (j = 1; j <= N; j++)
			scanf ("%d", &A[i][j]);
	for (i = 1; i <= N; i++)
		for (j = 1; j <= N; j++)
			scanf ("%d", &B[i][j]);
	for (i = 1; i <= N; i++)
		for (j = 1; j <= N; j++)
			scanf ("%d %d %d %d\n", &c[i][j][0], &c[i][j][1], &c[i][j][2], &c[i][j][3]);

	fill (1, 1);


	printf ("%d\n", res);
	return 0;
}