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
| class Solution:
def numberOfPatterns(self, m: int, n: int) -> int:
def DFS(vis, skip, cur, remain):
if remain < 0:
return 0
if remain == 0:
return 1
vis[cur] = True
rst = 0
for i in range(1, 10):
if not vis[i] and (skip[cur][i] == 0 or vis[skip[cur][i]]):
rst += DFS(vis, skip, i, remain - 1)
vis[cur] = False
return rst
skip = [[0] * 10 for _ in range(10)]
skip[1][3] = skip[3][1] = 2
skip[1][7] = skip[7][1] = 4
skip[3][9] = skip[9][3] = 6
skip[7][9] = skip[9][7] = 8
skip[1][9] = skip[9][1] = skip[2][8] = skip[8][2] = skip[3][7] = skip[7][3] = skip[4][6] = skip[6][4] = 5
vis = [False] * 10
rst = 0
for i in range(m, n + 1):
rst += DFS(vis, skip, 1, i - 1) * 4 # 1, 3, 7, 9 are symmetric
rst += DFS(vis, skip, 2, i - 1) * 4 # 2, 4, 6, 8 are symmetric
rst += DFS(vis, skip, 5, i - 1) # 5
return rst
|