这道题读懂题意挺关键。题目的意思是，从一个位置到另一个位置有两种情况，一种情况是到上下左右或者四个对角相邻的位置，另一种情况通过相邻且已经被访问过的位置到另一个不相邻的位置 主要思想就是铜鼓obacktracking来访问所有可能的解法。为啥是backtracking呢，因为对于解法的长度有一个范围，也就是当前一种解法成立的时候，继续扩展下去还有可能形成新的解法，至于具体的实现也需要很巧妙的设计。参考这个网址，里面有对解法的具体设计有很详细的解释：https://leetcode.com/problems/android-unlock-patterns/discuss/874714/Simple-Python-Solution-with-Explaination
class Solution: def numberOfPatterns(self, m: int, n: int) -> int: def backtracking(curr_key,step): if step == 1: return 1 count = 0 seen[curr_key] = True for i in range(1,10): # just continue is the key i has been visited if seen[i]: continue # if key i not in d[curr_key],meaning it is a beighbor of curr_key if i not in d[curr_key]: count += backtracking(i,step-1) if i in d[curr_key] and seen[d[curr_key][i]]: count += backtracking(i,step-1) seen[curr_key] = False return count seen = [False]*10 total_way = 0 d = {1:{9:5,3:2,7:4}, 2:{8:5}, 3:{1:2,9:6, 7:5} , 4:{6:5},5:{}, 6:{4:5},7:{1:4,3:5,9:8}, 8:{2:5}, 9:{7:8,1:5,3:6}} for step in range(m,n+1): for curr_key in range(1,10): total_way += backtracking(curr_key,step) return total_way