To calculate 3 order pattern lock

1
#include <cstdio>
2
#include <cstring>
3
#define N 4
4
#define DIGIT N*N
5
#define THRESHOLD 4
6

7
using namespace std;
8

9
bool vis[DIGIT + 1];
10
long long int dp[DIGIT + 1][1<<(DIGIT + 1)][DIGIT + 1];
11
int ban_1[DIGIT + 1][DIGIT + 1] = {
12
        {0,/*0*/ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
13
    //   0       1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16
14
        {0,/*1*/ 0, 0, 2, 2, 0, 0, 0, 0, 5, 0, 6, 0, 5, 0, 0, 6},
15
        {0,/*2*/ 0, 0, 0, 3, 0, 0, 0, 0, 0, 6, 0, 7, 0, 6, 0, 0},
16
        {0,/*3*/ 2, 0, 0, 0, 0, 0, 0, 0, 6, 0, 7, 0, 0, 0, 7, 0},
17
        {0,/*4*/ 2, 3, 0, 0, 0, 0, 0, 0, 0, 7, 0, 8, 7, 0, 0, 8},
18
        {0,/*5*/ 0, 0, 0, 0, 0, 0, 6, 6, 0, 0, 0, 0, 9, 0,10, 0},
19
        {0,/*6*/ 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0,10, 0,11},
20
        {0,/*7*/ 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0,10, 0,11, 0},
21
        {0,/*8*/ 0, 0, 0, 0, 6, 7, 0, 0, 0, 0, 0, 0, 0,11, 0,12},
22
        {0,/*9*/ 5, 0, 6, 0, 0, 0, 0, 0, 0, 0,10,10, 0, 0, 0, 0},
23
        {0,/*10*/0, 6, 0, 7, 0, 0, 0, 0, 0, 0, 0,11, 0, 0, 0, 0},
24
        {0,/*11*/6, 0, 7, 0, 0, 0, 0, 0,10, 0, 0, 0, 0, 0, 0, 0},
25
        {0,/*12*/0, 7, 0, 8, 0, 0, 0, 0,10,11, 0, 0, 0, 0, 0, 0},
26
        {0,/*13*/5, 0, 0, 7, 9, 0,10, 0, 0, 0, 0, 0, 0, 0,14,14},
27
        {0,/*14*/0, 6, 0, 0, 0,10, 0,11, 0, 0, 0, 0, 0, 0, 0,15},
28
        {0,/*15*/0, 0, 7, 0,10, 0,11, 0, 0, 0, 0, 0,14, 0, 0, 0},
29
        {0,/*16*/6, 0, 0, 8, 0,11, 0,12, 0, 0, 0, 0,14,15, 0, 0}
30
};
31
int ban_2[DIGIT + 1][DIGIT + 1] = {
32
        {0,/*0*/ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
33
    //   0       1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16
34
        {0,/*1*/ 0, 0, 2, 3, 0, 0, 0, 0, 5, 0, 6, 0, 9, 0, 0,11},
35
        {0,/*2*/ 0, 0, 0, 3, 0, 0, 0, 0, 0, 6, 0, 7, 0,10, 0, 0},
36
        {0,/*3*/ 2, 0, 0, 0, 0, 0, 0, 0, 6, 0, 7, 0, 0, 0,11, 0},
37
        {0,/*4*/ 3, 3, 0, 0, 0, 0, 0, 0, 0, 7, 0, 8,10, 0, 0,12},
38
        {0,/*5*/ 0, 0, 0, 0, 0, 0, 6, 7, 0, 0, 0, 0, 9, 0,10, 0},
39
        {0,/*6*/ 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0,10, 0,11},
40
        {0,/*7*/ 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0,10, 0,11, 0},
41
        {0,/*8*/ 0, 0, 0, 0, 7, 7, 0, 0, 0, 0, 0, 0, 0,11, 0,12},
42
        {0,/*9*/ 5, 0, 6, 0, 0, 0, 0, 0, 0, 0,10,11, 0, 0, 0, 0},
43
        {0,/*10*/0, 6, 0, 7, 0, 0, 0, 0, 0, 0, 0,11, 0, 0, 0, 0},
44
        {0,/*11*/6, 0, 7, 0, 0, 0, 0, 0,10, 0, 0, 0, 0, 0, 0, 0},
45
        {0,/*12*/0, 7, 0, 8, 0, 0, 0, 0,11,11, 0, 0, 0, 0, 0, 0},
46
        {0,/*13*/9, 0, 0,10, 9, 0,10, 0, 0, 0, 0, 0, 0, 0,14,15},
47
        {0,/*14*/0,10, 0, 0, 0,10, 0,11, 0, 0, 0, 0, 0, 0, 0,15},
48
        {0,/*15*/0, 0,11, 0,10, 0,11, 0, 0, 0, 0, 0,14, 0, 0, 0},
49
        {0,/*16*/11,0, 0,12, 0,11, 0,12, 0, 0, 0, 0,15,15, 0, 0}
50
};
51

52
long long int dfs(int len, int pre, int status, bool is_zero) {
53
    if(len <= 0) return 1;
54

55
    if(!is_zero && dp[len][status][pre] != -1)
56
        return dp[len][status][pre];
57

58
    long long int sum = 0;
59
    for(int i = 0; i <= DIGIT; i++) {
60
        if(vis[i]) continue;
61

62
        if(is_zero) {
63
            if(!i) {
64
                if(len > THRESHOLD)
65
                    sum += dfs(len - 1, 0, 0, true);
66
            }
67
            else {
68
                vis[i] = true;
69
                sum += dfs(len - 1, i, 1<<i, false);
70
                vis[i] = false;
71
            }
72
        }
73
        else if(i) {
74
            if(!ban_1[pre][i] || (vis[ban_1[pre][i]] && vis[ban_2[pre][i]])) {
75
                vis[i] = true;
76
                sum += dfs(len - 1, i, (1<<i) + status, false);
77
                vis[i] = false;
78
            }
79
        }
80
    }
81

82
    if(!is_zero)
83
        dp[len][status][pre] = sum;
84

85
    return sum;
86
}
87

88
int main() {
89
    memset(vis, false, sizeof(vis));
90
    memset(dp, -1, sizeof(dp));
91
    printf("%lld\n", dfs(DIGIT, 0, 0, true));
92

93
    return 0;
94
}
95

96