HDU 1172(dfs)

亦凉 2022-09-20 11:23 106阅读 0赞

题意：如题。

#include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <cstring>
    #include <iostream>
    #define MIN( x, y ) (x) < (y) ? (x) : (y)
    using namespace std;
    
    struct Node
    {
        char num[10];
        int right, pos;    
    }n[105];
    
    void cmp( char *s, char *c, int &right, int &pos )
    {
        right = pos = 0;
        int shash[15] = {0};
        int chash[15] = {0}; 
        for( int i = 0; i < 4; ++i )
        {
            if( s[i] == c[i] )
                pos++;
        }
        for( int i = 0; i < 4; ++i )
        {
            shash[ s[i] ]++;
            chash[ c[i] ]++; 
        }
        for( int i = 0; i < 10; ++i )
        {
            right += MIN( shash[i], chash[i] ); 
        }
    }
    
    void getnext( char *s )
    {
        for( int i = 3; i >= 0; --i )
        {
            if( s[i] < 9 ) 
            {
                s[i]++;   
                return;
            }
            else
            {
                s[i] = 0;
            }
        }    
    }
    
    void DFS( bool &ans, int &num, int N )
    {
        int right, pos, flag, cnt = 0;
        char t[4] = {0};
        for( int i = 0; i < 10000; ++i )
        {
            flag = 0;
            for( int i = 0; i < N; ++i )
            {
                cmp( t, n[i].num, right, pos );
                if( right == n[i].right && pos == n[i].pos )
                    continue;
                else
                {
                    flag = 1;
                    break;
                }
            }    
            if( !flag )
            {
                ans = true;
                cnt++;
                num = t[0] * 1000 + t[1] * 100 + t[2] * 10 + t[3];
                if( cnt > 1 )
                {
                    ans = false;
                    return;    
                }
            }
            getnext( t );
        }
    }
    
    int main()
    {
        int N;
        while( scanf( "%d", &N ), N )
        {
            int num = 0;
            for( int i = 0; i < N; ++i )
            {
                scanf( "%s %d %d", n[i].num, &n[i].right, &n[i].pos );        
                for( int j = 0; j < 4; ++j )
                    n[i].num[j] -= '0';
            }
            bool ans = false;
            DFS( ans, num, N );
            if( ans ) 
                printf( "%d\n", num );
            else
                puts( "Not sure" );
        };
        return 0;
    }