Cod sursa(job #761900)

Utilizator titusuTitus C titusu Data 27 iunie 2012 20:09:00
Problema Zone Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
using namespace std;

#include <fstream>
#include <fstream>

int n, x[10],z[10], a[525][525] , l1 , l2 , c1 , c2;
long long s[525][525],v[10];

ifstream fin("zone.in");
ofstream fout("zone.out");

long long suma(int i1,int j1, int i2, int j2){
	return s[i2][j2] + s[i1-1][j1-1] - s[i1-1][j2] - s[i2][ j1-1 ];
}

void verif(){
	for(int i1=1 ; i1<n-1 ; i1++)
		for(int j1=1 ; j1 < n-1; j1++)
			if(suma(1,1,i1,j1)==v[x[1]])
				for(int j2=j1+1;j2<n ; ++j2)
					if(suma(1,j1+1,i1,j2) == v[x[2]] && suma(1,j2+1,i1,n) == v[x[3]])
						for(int i2=i1+1 ; i2<n ; ++i2)
							if(
								suma(i1+1,1,i2,j1) == v[x[4]] && suma(i1+1,j1+1,i2,j2) == v[x[5]] && suma(i1+1,j2+1,i2,n) == v[x[6]]
								&&
								suma(i2+1,1,n,j1) == v[x[7]] &&  suma(i2+1,j1+1,n,j2) == v[x[8]] &&  suma(i2+1,j2+1,n,n) == v[x[9]]
							){
								l1=i1, l2=i2, c1=j1, c2=j2;
								return;
							}
}

void back(int k){
	for(int i=1;i<10 && !l1;++i){
		if(z[i]==0){
			z[i]=1;
			x[k]=i;
			if(k==9)
				verif();
			else
				back(k+1);
			z[i]=0;
		}
	}
}

int main(){
	fin >> n;
	for(int i=1;i<=9;++i)
		fin >> v[i];
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j){
			fin >> a[i][j];
			s[i][j] = a[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1];
		}
	back(1);
	fout << l1 << " " << l2 << " " << c1 << " " << c2 << "\n";
	return 0;
}