Cod sursa(job #63400)

Utilizator m_dersidanDersidan Mihai m_dersidan Data 28 mai 2007 14:32:14
Problema Zone Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
# include <stdio.h>
# include <string.h>

# define  _fin	"zone.in"
# define  _fout	"zone.out"

# define  maxn	515


int s[maxn][maxn], n, l1, l2, c1, c2, a[10];

short int ca[maxn];

int i, j, k, x;
int s1, s2, s3, s4, s5, s6, s7, s8, s9;


# define  sum(x1,y1,x2,y2) ( s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1] )

int main()
{
	freopen(_fin, "r", stdin);
	freopen(_fout,"w", stdout);
	
	for (scanf("%d", &n), i=0; i<9; ++i) scanf("%d", a+i);
	
	for (i=1; i<=n; ++i)
		for (j=1; j<=n; ++j)
			scanf("%d", &x), s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + x;
	
	for (l1=1; l1<n; ++l1) {
		memset(ca, 0, sizeof(ca));
		
		for (c1=1; c1<n; ++c1)
			for (s1=0; s1<9; ++s1)
//			for (j=0; j<9; ++j)
				if ( sum(1, 1, l1, c1)==a[s1] ) {
					ca[s1] = 1;
					
					for (c2=c1+1; c2<=n; ++c2) {
						for (s2=0; s2<9; ++s2)
							if ( sum(1, c1+1, l1, c2)==a[s2] && !ca[s2] ) { ca[s2]=1; break; }
						for (s3=0; s3<9; ++s3)
							if ( sum(1, c2+1, l1, n )==a[s3] && !ca[s3] ) { ca[s3]=1; break; }
						
						if ( s2<9 && s3<9 ) {
							for (l2=l1+1; l2<=n; ++l2) {
								// other 6 sums
								for (s4=0; s4<9; ++s4)
									if ( sum(l1+1, 1, l2, c1)==a[s4] && !ca[s4] ) { ca[s4]=1; break; }
								for (s5=0; s5<9; ++s5)
									if ( sum(l1+1, c1+1, l2, c2)==a[s5] && !ca[s5] ){  ca[s5]=1; break; }
								for (s6=0; s6<9; ++s6)
									if ( sum(l1+1, c2+1, l2, n)==a[s6] && !ca[s6] ) { ca[s6]=1; break; }
								for (s7=0; s7<9; ++s7)
									if ( sum(l2+1, 1, n, c1)==a[s7] && !ca[s7] ) { ca[s7]=1; break; }
								for (s8=0; s8<9; ++s8)
									if ( sum(l2+1, c1+1, n, c2)==a[s8] && !ca[s8] ) { ca[s8]=1; break; }
								for (s9=0; s9<9; ++s9)
									if ( sum(l2+1, c2+1, n, n)==a[s9] && !ca[s9] ) { ca[s9]=1; break; }
								
								if ( s4<9 && s5<9 && s6<9 && s7<9 && s8<9 && s9<9 )
									goto found_sol;
								
								ca[s4] = ca[s5] = ca[s6] = ca[s7] = ca[s8] = ca[s9] = 0;
							}
						}
						
						ca[s2]=ca[s3]=0;
					}
					
					ca[s1] = 0;

					break;
				}
	}
	
	found_sol:
	printf("%d %d %d %d\n", l1, l2, c1, c2);
	
	return 0;
}