Password UVA - 1262——DFS

傷城~ 2022-06-15 09:29 87阅读 0赞

Think:  
1方法:  
1>数学规律+DFS or 数学规律+递推  
2>暴力枚举  
2反思:题意没有理解好，结果一直Wrong Answer(符合对应列都出现的元素没有去重)

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <algorithm>
    #include <cstring>
    
    using namespace std;
    
    int k, ans, tp, link[14], v[14][14];
    void Pre(char st1[14][14], char st2[14][14]);
    void DFS(int x);
    
    int main()
    {
        int T, i;
        char st1[14][14], st2[14][14];
        scanf("%d", &T);
        while(T--)
        {
        
            scanf("%d", &k);
            getchar();
            for(i = 0; i < 6; i++)
            {
        
                scanf("%s", st1[i]);
            }
            for(i = 0; i < 6; i++)
            {
        
                scanf("%s", st2[i]);
            }
    
            Pre(st1, st2);
    
            for(i = 0; i < 5; i++)
            {
        
                int m = v[i][0];
                sort(v[i]+1, v[i]+m+1);
            }
    
            tp = 0, ans = 0;
            DFS(0);
            if(tp == 5)
            {
        
                for(i = 0; i < tp; i++)
                    printf("%c", link[i]+'A');
                printf("\n");
            }
            else {
        
                printf("NO\n");
            }
        }
        return 0;
    }
    void DFS(int x)
    {
        int i, sum = 1;
        for(i = x+1; i < 5; i++){
        
            sum *= v[i][0];
        }
    
        for(i = 1; i <= v[x][0]; i++){
        
    
            if(k > ans && k <= ans + sum){
        
                link[tp++] = v[x][i];
                DFS(x+1);
                break;
            }
            ans += sum;
        }
    }
    void Pre(char st1[14][14], char st2[14][14])
    {
        bool u[44];
        for(int l = 0; l < 5; l++)
        {
        
            int t = 1;
            memset(u, true, sizeof(u));
            for(int i = 0; i < 6; i++)
            {
        
                for(int j = 0; j < 6; j++)
                {
        
                    int z = st1[i][l] - 'A';
                    if(st1[i][l] == st2[j][l] && u[z])
                    {
        
                        u[z] = false;
                        v[l][t++] = st1[i][l] - 'A';
                    }
                }
            }
            v[l][0] = t-1;
        }
    }

[vjudge]: https://vjudge.net/problem/UVA-1262