Cod sursa(job #1839894)

Utilizator leraValeria lera Data 3 ianuarie 2017 16:22:21
Problema Zone Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.6 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],l1,l2,c1,c2,suma[5];
int l1minim=550,l2minim=550,c1minim=550,c2minim=550,summin=999999999;
long long s[10],n;
int verif()
{
    int nr=0;
    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;
    if(sum[n][c1]!=v[1]+v[4]+v[5])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];
    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;
                nr++;
                break;
            }
    if(nr!=4)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())
                {
                    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;
}