poj 1166 The Clocks

1485 단어 Lock
http://poj.org/problem?id=1166
#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<map>

#include<cmath>

#define LL long long



using namespace std;



const int N=11;



char pre[N][10]=

{"" ,"ABDE","ABC" ,"BCEF","ADG","BDEFH" ,"CFI" ,"DEGH" ,"GHI" ,"EFHI"};

int a[N];

int ans[N];

int b[N];

int num;

void judge(int k)

{

    for(int i=1;i<=9;++i)

    {

        if(a[i]%4!=0)

        return ;

    }

    for(int i=1;i<=9;++i)

    ans[i]=b[i];

    num=k;

    return ;

}

void dfs(int x,int sum)

{

    for(int i=0;i<4;++i)

    {

        b[x]=i;

        for(int j=0;pre[x][j]!='\0';++j)

        a[pre[x][j]-'A'+1]+=i;

        if(x<9&&sum<num)

        dfs(x+1,sum+i);

        if(x==9&&sum+i<num)

        {

            judge(sum+i);

        }

        for(int j=0;pre[x][j]!='\0';++j)

        a[pre[x][j]-'A'+1]-=i;

    }

}

int main()

{

    num=40;

    for(int i=1;i<=9;++i)

    {

        scanf("%d",&a[i]);

    }

    dfs(1,0);

    for(int i=1;i<=9;++i)

    {

        while(ans[i]--)

        {

            printf("%d ",i);

        }

    }

    printf("
"); return 0; }

좋은 웹페이지 즐겨찾기