Cod sursa(job #1969777)

Utilizator 2016Teo@Balan 2016 Data 18 aprilie 2017 17:26:00
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.45 kb
# include <fstream>
# include <algorithm>
# include <vector>
# define DIM 522
# define a first.first
# define b first.second
# define c second.first
# define d second.second
using namespace std;
ifstream fin("zone.in");
ofstream fout("zone.out");
pair<pair<int,int>,pair<int,int> > sol[10000];
int v[DIM][DIM],n,i,j,k,l1,l2,c1,c2;
long long p[DIM][DIM],val[10];
vector <int> valori;

bool eSolutie(int a1, int a2, int a3, int a4, int a5, int a6, int a7, int a8, int a9)
{
    vector <int> v;
    v.push_back(a1);
    v.push_back(a2);
    v.push_back(a3);
    v.push_back(a4);
    v.push_back(a5);
    v.push_back(a6);
    v.push_back(a7);
    v.push_back(a8);
    v.push_back(a9);
    sort(v.begin(), v.end());
    for(int i = 0; i < valori.size(); i++)
    {
        //fout << valori[i] << " " <<v[i]<<"\n";
        if(valori[i] != v[i])
        {
            return false;
        }
    }

    return true;

}

int verifica(long long nr)
{
    for(int i=1; i<=9; i++)
        if(nr==val[i])
            return 1;
    return 0;
}
int main ()
{
    fin>>n;
    for(i=1; i<=9; i++)
    {
        fin>>val[i];
        valori.push_back(val[i]);
        {

        }
    }
    sort(valori.begin(), valori.end());

    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            fin>>v[i][j];
            p[i][j]=p[i-1][j]+p[i][j-1]-p[i-1][j-1]+v[i][j];
        }
    }
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            if(verifica(p[i][j]))
            {
                l1=i;
                c1=j;
                for(l2=l1+1; l2<=n; l2++)
                {
                    if(verifica(p[l2][j]-p[i][j]))
                    {
                        for(c2=c1+1; c2<=n; c2++)
                            if(verifica(p[l1][c2]-p[l1][c1]) &&
                                    verifica(p[l1][n]-p[l1][c2]) &&
                                    verifica(p[l2][c2]-p[l2][c1]-p[l1][c2]+p[l1][c1]) &&
                                    verifica(p[l2][n]-p[l2][c2]-p[l1][n]+p[l1][c2]) &&
                                    verifica(p[n][c1]-p[l2][c1]) &&
                                    verifica(p[n][c2]-p[n][c1]-p[l2][c2]+p[l2][c1]) &&
                                    verifica(p[n][n]-p[l2][n]-p[n][c2]+p[l2][c2]))
                            {
                                if(eSolutie(p[i][j],p[l2][j]-p[i][j],
                                            p[l1][c2]-p[l1][c1],p[l1][n]-p[l1][c2],
                                            p[l2][c2]-p[l2][c1]-p[l1][c2]+p[l1][c1],
                                            p[l2][n]-p[l2][c2]-p[l1][n]+p[l1][c2],
                                            p[n][c1]-p[l2][c1],
                                            p[n][c2]-p[n][c1]-p[l2][c2]+p[l2][c1],
                                            p[n][n]-p[l2][n]-p[n][c2]+p[l2][c2]))
                                {
                                    sol[++k].a=l1;
                                    sol[k].b=c1;
                                    sol[k].c=l2;
                                    sol[k].d=c2;
                                }

                                //fout << l1 << " " <<c1<<" "<<l2<<" "<<c2<<"\n";
                            }
                    }
                }
            }
        }
    }
    sort(sol+1,sol+k+1);
    fout<<sol[1].a<<" "<<sol[1].c<<" "<<sol[1].b<<" "<<sol[1].d<<"\n";

    return 0;
}