2014年10月5日 星期日

2014/10/05 codevs 1064 虫食算 2004年NOIP全国联赛提高组

/*
    DFS 

    對於 A+B=C A,B,C中 任兩者已決定了
    那另一個便直接決定 這是一個剪枝

    另外從N-1枚舉到0 貌似會比較快
*/
// http://codevs.cn/problem/1064/
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

int N;
int A[90];

bool use[30]; int num[30];

bool DFS(int O, int carry)
{
    if( O == N*3 )
    {
        for(int Ni = 0; Ni < N; Ni++)
        {
            printf("%d", num[Ni]);

            if( Ni == N-1 ) puts("");
            else printf(" ");
        }
        return true;
    }

    if( O%3 == 2 )
    {
        int P = (num[A[O-2] ]+num[A[O-1] ]+carry)%N;
        int Q = (num[A[O-2] ]+num[A[O-1] ]+carry)/N;

        if( num[A[O] ] != -1 )
        {
            if( num[A[O] ] != P ) return false;
            return DFS(O+1, Q);
        }
        else
        {
            if( use[P] ) return false;
            use[P] = true;
            num[A[O] ] = P;

            if( DFS(O+1, Q) ) return true;

            use[P] = false;
            num[A[O] ] = -1;
            return false;
        }

    }
    else
    {
        if( num[A[O/3*3+2 ] ] != -1 && num[A[O/3*3+1-O%3] ] != -1 )
        {
            int P = (num[A[O/3*3+2 ] ]-num[A[O/3*3+1-O%3] ]-carry+N)%N;

            if( num[A[O] ] != -1 )
            {
                if( num[A[O] ] != P ) return false;
                return DFS(O+1, carry);
            }
            else
            {
                if( use[P] ) return false;
                use[P] = true;
                num[A[O] ] = P;

                if( DFS(O+1, carry) ) return true;

                use[P] = false;
                num[A[O] ] = -1;
                return false;
            }
        }

        if( num[A[O] ] != -1 ) return DFS(O+1, carry);

        for(int Ni = N-1; Ni >= 0; Ni--)
            if( !use[Ni] )
            {
                use[Ni] = true;
                num[A[O] ] = Ni;

                if( DFS(O+1, carry) ) return true;

                use[Ni] = false;
                num[A[O] ] = -1;
            }

        return false;

    }
}

int main()
{
    scanf("%d", &N);

    for(int i = 0; i < 3; i++)
    {
        char C[30];
        scanf("%s", C);

        for(int Ni = 0; Ni < N; Ni++)
            A[Ni*3+i] = C[N-1-Ni]-'A';
    }

    fill(use, use+30, false);
    fill(num, num+30, -1);

    DFS(0, 0);
}

沒有留言:

張貼留言