Cod sursa(job #431722)

Utilizator freak93Adrian Budau freak93 Data 1 aprilie 2010 12:37:08
Problema Copii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<cstdio>
#include<cstring>

using namespace std;

const char iname[]="copii.in";
const char oname[]="copii.out";
const int maxn=12;

char s[maxn][maxn];

int i,j,n,ec[maxn],a[maxn][maxn],k,rez;

int test()
{
    memset(a,0,sizeof(a));
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            if(s[i][j])
                a[ec[i]][ec[j]]=1;
    for(i=1;i<=k;++i)
        for(j=1;j<=k;++j)
            if(a[i][j]==0)
                return 0;
    return 1;
}

void back(int x)
{
    if(x>n)
    {
        if(k>1)
            rez+=test();
        return;
    }
    for(int i=1;i<=k;++i)
        ec[x]=i,back(x+1);
    ec[x]=++k;
    back(x+1);
    --k;
}

int main()
{
    freopen(iname,"r",stdin);
    freopen(oname,"w",stdout);

    scanf("%d\n",&n);
    for(i=1;i<=n;++i)
        fgets(s[i]+1,sizeof(s[i]),stdin);
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            s[i][j]-='0';
    for(i=1;i<=n;++i)
        s[i][i]=1;
    back(1);
    printf("%d\n",rez);

    fclose(stdin);
    fclose(stdout);

    return 0;
}