Pagini recente » Cod sursa (job #534931) | Cod sursa (job #2297690) | Cod sursa (job #143015) | Cod sursa (job #844592) | Cod sursa (job #2197760)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in ("zone.in");
ofstream out ("zone.out");
int v[520][520],s[520][520],val[11],vv[11],n;
int col (int poz, int i, int j)
{
int pas=1<<10,k=poz;
while(pas)
{
if(k+pas<=n && s[i][k+pas]-s[i][poz-1]<=val[j])
k+=pas;
pas>>=1;
}
if(s[i][k]-s[i][poz-1]==val[j])
return k;
return -1;
}
int lin (int poz, int i, int j)
{
int pas=1<<10,k=poz;
while(pas)
{
if(k+pas<=n && s[k+pas][i]-s[poz-1][i]<=val[j])
k+=pas;
pas>>=1;
}
if(s[k][i]-s[poz-1][i]==val[j])
return k;
return -1;
}
bool verif (int l1, int l2, int c1, int c2)
{
vv[1]=s[l1][c1];
vv[2]=s[l1][c2]-vv[1];
vv[3]=s[l1][n]-s[l1][c2];
vv[4]=s[l2][c1]-vv[1];
vv[5]=s[l2][c2]-s[l1][c2]-s[l2][c1]+vv[1];
vv[6]=s[l2][n]-s[l2][c2]-vv[3];
vv[7]=s[n][c1]-s[l2][c1];
vv[8]=s[n][c2]-s[l2][c2]-vv[7];
vv[9]=s[n][n]-s[l2][n]-s[n][c2]+s[l2][c2];
sort(vv+1,vv+10);
for(int i=1;i<=9;i++)
if(vv[i]!=val[i])
return false;
return true;
}
int main()
{
int i,j,a,b,c,jj,jjj;
in>>n;
for(i=1;i<=9;i++)
in>>val[i];
sort(val+1,val+10);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
in>>v[i][j];
s[i][j]=v[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}
for(i=1;i<=n;i++)
{
for(j=1;j<=9;j++)
{
a=col(1,i,j);
if(a==-1)
continue;
for(jj=1;jj<=9;jj++)
{
if(jj!=j)
{
b=col(a+1,i,jj);
if(b==-1)
continue;
for(jjj=1;jjj<=9;jjj++)
{
if(jjj!=jj && jjj!=j)
{
c=lin(i+1,a,jjj);
if(c==-1)
continue;
if(verif(i,c,a,b))
{
out<<i<<' '<<c<<' '<<a<<' '<<b;
i=n+1;
j=jj=jjj=1000;
break;
}
}
}
}
}
}
}
return 0;
}