Cod sursa(job #542397)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 26 februarie 2011 12:55:25
Problema Pixels Scor 10
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 1.23 kb
#include <fstream>
using namespace std;
ifstream fin("pixels.in");
ofstream fout("pixels.out");

#define maxn 105

const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};
int i,j,k,N,S,MaxS;
int A[maxn][maxn],B[maxn][maxn],C[maxn][maxn][4],P[maxn][maxn];
bool inS[maxn][maxn];

void citire()
{
	fin >> N;
	for(i=1;i<=N;i++)
		for(j=1;j<=N;j++)
			fin >> A[i][j];
	for(i=1;i<=N;i++)
		for(j=1;j<=N;j++)
			fin >> B[i][j];
	for(i=1;i<=N;i++)
		for(j=1;j<=N;j++)
			for(k=0;k<4;k++)
				fin >> C[i][j][k];
}

void suma()
{
	S=0;
	for(i=1;i<=N;i++)
		for(j=1;j<=N;j++)
			if(P[i][j]==0) S+=A[i][j];
			else S+=B[i][j];
	if(S<MaxS) return;
	for(i=1;i<=N;i++)
		for(j=1;j<=N;j++)
		{
			if(S<MaxS) return;
			if(P[i][j]!=P[i][j+1])
				S-=C[i][j][1];
			if(P[i][j]!=P[i+1][j])
				S-=C[i][j][2];
		}
	if(S>MaxS) MaxS=S;
}

void back(int p,int x, int y)
{
	int d;
	P[x][y]=0;
	inS[x][y]=1;
	while(P[x][y]<2)
	{
		if(p==N*N) suma();
		else
		for(d=0;d<4;d++)
			if(x+dx[d]>=1 && x+dx[d]<=N && y+dy[d]>=1 && y+dy[d]<=N)
				if(!inS[x+dx[d]][y+dy[d]])
				{
					back(p+1,x+dx[d],y+dy[d]);
					break;
				}
		P[x][y]++;
	}
	inS[x][y]=0;
}

int main()
{
	citire();
	back(1,1,1);
	fout << MaxS;
}