• Time:O(n!)
• Space:O(n)

## C++

class Solution {
public:
int numberOfPatterns(int m, int n) {
int ans = 0;
vector<vector<int>> across(10, vector<int>(10));
vector<bool> seen(10);

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

ans += dfs(m, n, 1, 1, seen, across) * 4;  // 1, 3, 7, 9 are symmetric
ans += dfs(m, n, 2, 1, seen, across) * 4;  // 2, 4, 6, 8 are symmetric
ans += dfs(m, n, 5, 1, seen, across);      // 5
return ans;
}

private:
int dfs(int m, int n, int u, int depth, vector<bool>& seen,
const vector<vector<int>>& across) {
if (depth > n)
return 0;

seen[u] = true;
int ans = depth >= m ? 1 : 0;

for (int v = 1; v <= 9; ++v) {
if (v == u || seen[v])
continue;
const int acrossed = across[u][v];
if (acrossed == 0 || seen[acrossed])
ans += dfs(m, n, v, depth + 1, seen, across);
}

seen[u] = false;
return ans;
}
};

## JAVA

class Solution {
public int numberOfPatterns(int m, int n) {
int ans = 0;
int[][] across = new int[10][10];
boolean[] seen = new boolean[10];

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

ans += dfs(m, n, 1, 1, seen, across) * 4; // 1, 3, 7, 9 are symmetric
ans += dfs(m, n, 2, 1, seen, across) * 4; // 2, 4, 6, 8 are symmetric
ans += dfs(m, n, 5, 1, seen, across);     // 5
return ans;
}

private int dfs(int m, int n, int u, int level, boolean[] seen, int[][] across) {
if (level > n)
return 0;

seen[u] = true;
int ans = level >= m;

for (int v = 1; v <= 9; ++v) {
if (v == u || seen[v])
continue;
final int acrossed = across[u][v];
if (acrossed == 0 || seen[acrossed])
ans += dfs(m, n, v, level + 1, seen, across);
}

seen[u] = false;
return ans;
}
}

## Python

class Solution:
def numberOfPatterns(self, m: int, n: int) -> int:
seen = set()
accross = [[0] * 10 for _ in range(10)]

accross[1][3] = accross[3][1] = 2
accross[1][7] = accross[7][1] = 4
accross[3][9] = accross[9][3] = 6
accross[7][9] = accross[9][7] = 8
accross[1][9] = accross[9][1] = accross[2][8] = accross[8][2] = \
accross[3][7] = accross[7][3] = accross[4][6] = accross[6][4] = 5

def dfs(u: int, depth: int) -> int:
if depth > n:
return 0

ans = 1 if depth >= m else 0

for v in range(1, 10):
if v == u or v in seen:
continue
accrossed = accross[u][v]
if not accrossed or accrossed in seen:
ans += dfs(v, depth + 1)

seen.remove(u)
return ans

# 1, 3, 7, 9 are symmetric
# 2, 4, 6, 8 are symmetric
return dfs(1, 1) * 4 + dfs(2, 1) * 4 + dfs(5, 1)