Cod sursa(job #2636957)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 20 iulie 2020 19:27:58
Problema Copii Scor 90
Compilator cpp-32 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <bits/stdc++.h>
#define DIM 15
using namespace std;

bool v[DIM][DIM];
vector <pair<short,short> > mch;
pair <short,short> x[DIM];
char s[DIM];
int n,i,j,sol;


void back (short pas){

    if (pas == n+1){

        short k = x[n].second;

        if (k == 1)
            return;

        for (short i=1;i<=k;++i)
            for (short j=1;j<=k;++j)
                v[i][j] = 0;
        short cnt = 0;
        for (auto it : mch){
            short a = it.first, b = it.second;
            short g1 = x[a].first, g2 = x[b].first;
            if (!v[g1][g2] && g1 != g2)
                ++cnt;

            v[g1][g2] = 1;
        }

        if (cnt == (k-1)*k)
            ++sol;

        return;
    }

    for (short i=1;i<=n;++i){

        x[pas].first = i;
        if (x[pas].first <= x[pas-1].second+1){
            x[pas].second = max (x[pas-1].second,i);
            back(pas+1);
            x[pas].second = x[pas-1].second;
        }}}


int main (){

    ifstream fin ("copii.in");
    ofstream fout ("copii.out");

    fin>>n;
    for (i=1;i<=n;++i){
        fin>>s+1;
        for (j=1;j<=n;++j)
            if (s[j] == '1')
                mch.push_back(make_pair(i,j));
    }

    back(1);

    fout<<sol;

    return 0;
}