Cod sursa(job #1839846)

Utilizator leraValeria lera Data 3 ianuarie 2017 15:21:10
Problema Zone Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 kb
#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],fr[10],v[10],fr2[10],ok,l1,l2,c1,c2,suma[5];
long long s[10],n;
int verif()
{
    for(int i=1;i<=9;i++)
        fr2[i]=fr[i];
    for(int i=1;i<=n;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;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;
    if(sum[n][c1]!=v[1]+v[4]+v[5])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];
    for(int j=1;j<=4;j++)
        for(int i=1;i<=9;i++)
            if(fr2[i]==0 && suma[j]==s[i])
            {
                fr2[i]=1;
                break;
            }
    for(int i=1;i<=9;i++)
        if(fr2[i]==0)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==5)
            {
                c1=0;l1=0;l2=0;c2=0;
                if(verif() && ok==0)
                {
                    fout<<l1<<" "<<l2<<" "<<c1<<" "<<c2;
                    ok=1;
                }
            }
            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);
    return 0;
}