Cod sursa(job #2456005)

Utilizator Coroian_DavidCoroian David Coroian_David Data 13 septembrie 2019 12:20:33
Problema Oras Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.97 kb
#include <bits/stdc++.h>

#define MAX_N 200

using namespace std;

int n;
int q[10];
int d[10];

int a[MAX_N + 1][MAX_N + 1];

const int sqrInf = (int)(1e9);

void readFile()
{
    ifstream f("oras.in");

    f >> n;

    f.close();
}

int viz;

void bfs(int start)
{
    int dr = 1, st = 0;
    q[++ st] = start;
    d[start] = 0;
    while(st <= dr)
    {
        int cr = q[st ++];
        for(int u = 1; u <= 6; u ++)
        {
            if(a[cr][u] == 1)
            if(d[cr] + 1 < d[u])
            {
                d[u] = d[cr] + 1;
                q[++ dr] = u;
            }
        }
    }
}

void verif()
{
    int ok = 1;
    for(int i = 1; i <= 6; i ++)
    {
        for(int j = 1; j <= 6; j ++)
            d[j] = sqrInf;
        bfs(i);

       // cout << " pentru i" << "\n";
        for(int j = 1; j <= 6; j ++)
        {
           // cout << d[j] << " ";

            if(d[j] > 2)
                ok = 0;
        }
    }

    if(ok)
    {
        cout << "GASIT\n";

        ofstream g("oras.out");

        if(n == 4)
            g << "-1\n";

        else
        for(int i = 1; i <= n; i ++)
        {
            for(int j = 1; j <= n; j ++)
                g << a[i][j];

            g << "\n";
        }

        g.close();
        exit(0);
    }
}

void bkt(int k, int st)
{
    if(k == 6)
    {
        verif();

        return;
    }

    for(int i = st; i <= 6; i ++)
    {
        a[k][i] = 0;
        a[i][k] = 1;

        if(i == 6)
            bkt(k + 1, k + 2);
        else
            bkt(k, st + 1);

        a[k][i] = 1;
        a[i][k] = 0;

        if(i == 6)
            bkt(k + 1, k + 2);
        else
            bkt(k, st + 1);
    }
}

void solve()
{
    if(n == 4)
        return;

    if(n & 1)
    {
        a[1][2] = 1;
        a[2][3] = 1;
        a[3][1] = 1;

        for(int i = 4; i + 1 <= n; i += 2)
        {
            a[i][i + 1] = 1;
            for(int j = 1; j < i; j ++)
            {
                a[j][i] = 1;
                a[i + 1][j] = 1;
            }
        }
    }

    else
    {
        //bkt(1, 2);

        a[1][5] = a[1][6] = 1;
        a[2][1] = a[2][6] = 1;
        a[3][1] = a[3][2] = a[3][5] = 1;
        a[4][1] = a[4][2] = a[4][3] = 1;
        a[5][2] = a[5][4] = 1;
        a[6][3] = a[6][4] = a[6][5] = 1;

        for(int i = 7; i + 1 <= n; i += 2)
        {
            a[i][i + 1] = 1;
            for(int j = 1; j < i; j ++)
            {
                a[j][i] = 1;
                a[i + 1][j] = 1;
            }
        }
    }
}

void printFile()
{
    ofstream g("oras.out");

    if(n == 4)
        g << "-1\n";

    else
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= n; j ++)
            g << a[i][j];

        g << "\n";
    }

    g.close();
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}