Pagini recente » Cod sursa (job #1655844) | Cod sursa (job #1510412) | Cod sursa (job #206671) | Cod sursa (job #376774) | Cod sursa (job #1839920)
#include <iostream>
#include <fstream>
#define Nmax 520
using namespace std;
ifstream fin("zone.in");
ofstream fout("zone.out");
long long a[Nmax][Nmax],sum[Nmax][Nmax],suma[7];
int l1minim=550,l2minim=550,c1minim=550,c2minim=550,summin=999999999,l1,l2,c1,c2,fr[10],v[10],fr2[10],n;
long long s[10];
int verif()
{
int nr=0;
for(int i=1;i<=9;i++)
fr2[i]=fr[i];
for(int i=1;i<n-1;i++)
if(sum[i][n]==v[1]+v[2]+v[3])
{
l1=i;
break;
}
if(l1==0)return 0;
for(int j=1;j<n-1;j++)
if(sum[l1][j]==v[1])
{
c1=j;
break;
}
if(c1==0)return 0;
for(int j=c1+1;j<n;j++)
if(sum[l1][j]==v[1]+v[2])
{
c2=j;
break;
}
if(c2==0)return 0;
for(int i=l1+1;i<n;i++)
if(sum[i][c1]==v[1]+v[4])
{
l2=i;
break;
}
if(l2==0)return 0;
suma[1]=sum[l2][c2]-sum[l1][c2]-sum[l2][c1]+sum[l1][c1];
suma[2]=sum[l2][n]-sum[l1][n]-sum[l2][c2]+sum[l1][c2];
suma[3]=sum[n][c2]-sum[l2][c2]-sum[n][c1]+sum[l2][c1];
suma[4]=sum[n][n]-sum[l2][n]-sum[n][c2]+sum[l2][c2];
suma[5]=sum[n][c1]-sum[l2][c1];
for(int j=1;j<=5;j++)
for(int i=1;i<=9;i++)
if(fr2[i]==0 && suma[j]==s[i])
{
fr2[i]=1;
nr++;
break;
}
if(nr!=5)return 0;
return 1;
}
void bk(int k)
{
for(int i=1;i<=9;i++)
{
if(fr[i]==0)
{
v[k]=s[i];
fr[i]=1;
if(k==4)
{
c1=0;l1=0;l2=0;c2=0;
if(verif())
{
if(l1==l1minim)
{
if(c1==c1minim)
{
if(l2==l2minim)
{
if(l1+l2+c1+c2<summin)
{
l1minim=l1;
l2minim=l2;
c1minim=c1;
c2minim=c2;
}
}
else if(l2<l2minim)
{
l1minim=l1;
l2minim=l2;
c1minim=c1;
c2minim=c2;
}
}
else if(c1<c1minim)
{
l1minim=l1;
l2minim=l2;
c1minim=c1;
c2minim=c2;
}
}
if(l1<l1minim)
{
l1minim=l1;
l2minim=l2;
c1minim=c1;
c2minim=c2;
}
summin=l1minim+l2minim+c1minim+c2minim;
}
}
else bk(k+1);
fr[i]=0;
}
}
}
int main()
{
int i,j;
fin>>n;
for(i=1;i<=9;i++)fin>>s[i];
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++)
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
bk(1);
fout<<l1minim<<" "<<l2minim<<" "<<c1minim<<" "<<c2minim;
return 0;
}