Cod sursa(job #2482289)

Utilizator stefzahZaharia Stefan Tudor stefzah Data 27 octombrie 2019 23:51:11
Problema Zone Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.3 kb
#include <iostream>
#include <fstream>
#include <unordered_map>
using namespace std;
ifstream fin("zone.in");
ofstream fout("zone.out");
long long N;
long long a[10], v[550][550], l1, l2, c1, c2, s[550][550];
unordered_map<long long,long long>MAP,MAP1;
bool Check(long long x1, long long y1, long long x2, long long y2) {
    long long i;
    for (i = 1; i <= 9; i++)
        if (s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] == a[i])return true;
    return false;
}

bool Check2(long long x1, long long y1, long long x2, long long y2) {
    long long ct = 0;
        MAP1=MAP;
        if (MAP1[s[N][N] - s[x2][N] - s[N][y2] + s[x2][y2]]>0){MAP1[s[N][N] - s[x2][N] - s[N][y2] + s[x2][y2]]--;}
        else return false;
        if (MAP1[s[N][y2] - s[x2][y2] - s[N][y1] + s[x2][y1]]>0){MAP1[s[N][y2] - s[x2][y2] - s[N][y1] + s[x2][y1]]--;}
        else return false;
        if (MAP1[s[x2][N] - s[x1][N] - s[x2][y2] + s[x1][y2]]>0){MAP1[s[x2][N] - s[x1][N] - s[x2][y2] + s[x1][y2]]--;}
        else return false;
        if (MAP1[s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1]]>0){MAP1[s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1]]--;}
        else return false;
        if (MAP1[s[x1][N] - s[0][N] - s[x1][y2] + s[0][y2]]>0){MAP1[s[x1][N] - s[0][N] - s[x1][y2] + s[0][y2]]--;}
        else return false;
        if (MAP1[s[x1][y2] - s[0][y2] - s[x1][y1] + s[0][y1]]>0){MAP1[s[x1][y2] - s[0][y2] - s[x1][y1] + s[0][y1]]--;}
        else return false;
        if (MAP1[s[x1][y1] - s[0][y1] - s[x1][0] + s[0][0]]>0){MAP1[s[x1][y1] - s[0][y1] - s[x1][0] + s[0][0]]--;}
        else return false;
        if (MAP1[s[N][y1] - s[x2][y1] - s[N][0] + s[x2][0]]>0){MAP1[s[N][y1] - s[x2][y1] - s[N][0] + s[x2][0]]--;}
        else return false;
        if (MAP1[s[x2][y1] - s[x1][y1] - s[x2][0] + s[x1][0]]>0){MAP1[s[x2][y1] - s[x1][y1] - s[x2][0] + s[x1][0]]--;}
        else return false;
        return true;
}
bool Check3(long long x1, long long y1, long long x2)
{
    long long ct = 0;
    MAP1=MAP;
    if (MAP1[s[x1][y1] - s[0][y1] - s[x1][0] + s[0][0]]>0){ct++;MAP1[s[x1][y1] - s[0][y1] - s[x1][0] + s[0][0]]--;}
    if (MAP1[s[N][y1] - s[x2][y1] - s[N][0] + s[x2][0]]>0){ct++;MAP1[s[N][y1] - s[x2][y1] - s[N][0] + s[x2][0]]--;}
    if (MAP1[s[x2][y1] - s[x1][y1] - s[x2][0] + s[x1][0]]>0){ct++;MAP1[s[x2][y1] - s[x1][y1] - s[x2][0] + s[x1][0]]--;}
    return ct==3;
}
long long main() {
    long long i, j;
    fin >> N;
    for (i = 1; i <= 9; i++)
    {fin >> a[i];
     MAP[a[i]]++;
    }
    for (i = 1; i <= N; i++)
        for (j = 1; j <= N; j++) {
            fin >> v[i][j];
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + v[i][j];
        }
    for (l1 = 1; l1 < N - 1; l1++)
        for (c1 = 1; c1 < N - 1; c1++) {
            if (Check(1, 1, l1, c1) == 1) {
                //cout << "*" << s[l1][c1] << endl;
                for (l2 = l1 + 1; l2 < N; l2++) {
                    if(Check3(l1,c1,l2))
                    for (c2 = c1 + 1; c2 < N; c2++)
                        if (Check2(l1, c1, l2, c2)) {
                            fout << l1 << " " << l2 << " " << c1 << " " << c2;
                            l1 = N;
                            l2 = N;
                            c2 = N;
                            c1 = N;
                            break;
                        }
                }
            }
        }
}