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

7
using namespace std;
8

9
bool vis[DIGIT + 1];
10
int dp[DIGIT + 1][1<<(DIGIT + 1)][DIGIT + 1];
11
int ban[DIGIT + 1][DIGIT + 1] = {
12
    {0,/*0*/ 0, 0, 0, 0, 0, 0, 0, 0, 0},
13
//   0       1  2  3  4  5  6  7  8  9
14
    {0,/*1*/ 0, 0, 2, 0, 0, 0, 4, 0, 5},
15
    {0,/*2*/ 0, 0, 0, 0, 0, 0, 0, 5, 0},
16
    {0,/*3*/ 2, 0, 0, 0, 0, 0, 5, 0, 6},
17
    {0,/*4*/ 0, 0, 0, 0, 0, 5, 0, 0, 0},
18
    {0,/*5*/ 0, 0, 0, 0, 0, 0, 0, 0, 0},
19
    {0,/*6*/ 0, 0, 0, 5, 0, 0, 0, 0, 0},
20
    {0,/*7*/ 4, 0, 5, 0, 0, 0, 0, 0, 8},
21
    {0,/*8*/ 0, 5, 0, 0, 0, 0, 0, 0, 0},
22
    {0,/*9*/ 5, 0, 6, 0, 0, 0, 8, 0, 0}
23
};
24

25
int dfs(int len, int pre, int status, bool is_zero) {
26
    if(len <= 0) return 1;
27

28
    if(!is_zero && dp[len][status][pre] != -1)
29
        return dp[len][status][pre];
30

31
    int sum = 0;
32
    for(int i = 0; i <= DIGIT; i++) {
33
        if(vis[i]) continue;
34

35
        if(is_zero) {
36
            if(!i) {
37
                if(len > THRESHOLD)
38
                    sum += dfs(len - 1, 0, 0, true);
39
            }
40
            else {
41
                vis[i] = true;
42
                sum += dfs(len - 1, i, 1<<i, false);
43
                vis[i] = false;
44
            }
45
        }
46
        else if(i) {
47
            if(ban[pre][i] && vis[ban[pre][i]] == false) continue;
48
            else {
49
                vis[i] = true;
50
                sum += dfs(len - 1, i, (1<<i) + status, false);
51
                vis[i] = false;
52
            }
53
        }
54
    }
55

56
    if(!is_zero)
57
        dp[len][status][pre] = sum;
58

59
    return sum;
60
}
61

62
int main() {
63
    memset(vis, false, sizeof(vis));
64
    memset(dp, -1, sizeof(dp));
65
    printf("%d\n", dfs(DIGIT, 0, 0, true));
66

67
    return 0;
68
}
69