Leetcode 351. Android Unlock Patterns (python)

题目

解法：backtracking

这道题读懂题意挺关键。题目的意思是，从一个位置到另一个位置有两种情况，一种情况是到上下左右或者四个对角相邻的位置，另一种情况通过相邻且已经被访问过的位置到另一个不相邻的位置
主要思想就是铜鼓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 1count = 0seen[curr_key] = Truefor i in range(1,10):# just continue is the key i has been visitedif seen[i]:continue# if key i not in d[curr_key],meaning it is a beighbor of curr_keyif 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] = Falsereturn countseen = [False]*10total_way = 0d = {
    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