Notes/SlideUnlock 2.cpp at master · AgateLee/Notes · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <iostream>
#include <cstring>
using namespace std;

int ban[10][10];
int line[10];
int total[10];
bool v[10];
int dp[10][1024][10][10];

void init()
{
    memset(ban, 0, sizeof(ban));

    ban[1][3] = ban[3][1] = 2;
    ban[4][6] = ban[6][4] = 5;
    ban[7][9] = ban[9][7] = 8;
    ban[1][7] = ban[7][1] = 4;
    ban[2][8] = ban[8][2] = 5;
    ban[3][9] = ban[9][3] = 6;
    ban[1][9] = ban[9][1] = 5;
    ban[3][7] = ban[7][3] = 5;
}

int dfs(int len, int state, int pre, int gp, int use, int dest, bool zero)
{
    if(len <= 0)
    {
        if(use == dest)
            return 1;
        else
            return 0;
    }

    if(!zero && dp[len][state][pre][gp] != -1)
        return dp[len][state][pre][gp];

    int sum = 0;
    for(int i = 0; i <= 9; i++)
    {
        if(v[i])
            continue;

        if(zero)
        {
            if(!i)
            {
                if(len > 4)
                    sum += dfs(len - 1, 0, 0, 0, 0, dest, true);
            }
            else
            {
                if(total[pre] == 2)
                    continue;

                v[i] = true;
                sum += dfs(len - 1, 1<<i, i, 0, 0, dest, false);
                v[i] = false;
            }
        }
        else if(i)
        {
            if(ban[pre][i] && v[ban[pre][i]] == false)
            {
                continue;
            }
            else if((total[pre] > 0 || total[i] == 2) && !((line[pre]>>i) & 1))
            {
                continue;
            }
            else
            {
                int flag = 0;

                if(total[i] == 1 && ((line[pre]>>i) & 1)) //与前项满足
                {
                    flag = 1;
                    total[i] = 0;
                }

                v[i] = true;
                sum += dfs(len - 1, (1<<i) + state, i, pre, use + ((line[pre]>>i) & 1), dest, false);
                v[i] = false;

                if(flag)
                    total[i] = 1;
            }
        }
    }

    if(!zero)
        dp[len][state][pre][gp] = sum;

    return sum;
}

int main()
{
    init();

    int T, N, a, b;

    scanf("%d", &T);

    while(T --)
    {
        scanf("%d", &N);
        memset(v, false, sizeof(v));
        memset(dp, -1, sizeof(dp));
        memset(line, 0, sizeof(line));
        memset(total, 0, sizeof(total));

        for(int i = 1; i <= N; i++)
        {
            scanf("%d %d", &a, &b);
            line[a] |= (1<<b);
            line[b] |= (1<<a);
            total[a] ++;
            total[b] ++;
        }

        printf("%d\n", dfs(9, 0, 0, 0, 0, N, true));
    }

    return 0;
}