leetcode351

Description

Given an Android 3x3 key lock screen and two integers m and n, where 1 ≤ m ≤ n ≤ 9, count the total number of unlock patterns of the Android lock screen, which consist of minimum of m keys and maximum n keys.

Rules for a valid pattern:

1. Each pattern must connect at least m keys and at most n keys.
2. All the keys must be distinct.
3. If the line connecting two consecutive keys in the pattern passes through any other keys, the other keys must have previously selected in the pattern. No jumps through non selected key is allowed.
4. The order of keys used matters.

Example

| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |

Invalid move: 4 - 1 - 3 - 6
Line 1 - 3 passes through key 2 which had not been selected in the pattern.

Invalid move: 4 - 1 - 9 - 2
Line 1 - 9 passes through key 5 which had not been selected in the pattern.

Valid move: 2 - 4 - 1 - 3 - 6
Line 1 - 3 is valid because it passes through key 2, which had been selected in the pattern

Valid move: 6 - 5 - 4 - 1 - 9 - 2
Line 1 - 9 is valid because it passes through key 5, which had been selected in the pattern.

Example:
Given m = 1, n = 1, return 9.

Idea

这种棋盘格子之类的问题往往是用dfs来求解的。然后，discussion里面这个哥们给的解挺好的，很清晰：
The basic idea is starting from an arbitrary digit (prev), search all the valid next digit. Use a set/dict (visited) to store all the visited digits. What is the invalid combination? Only two cases.

if prev in {1, 3, 7, 9} and next in {1, 3, 7, 9}, however, (prev + next)/2 not in visited. e.g. 1 -> 7 and 4 not visited.
if prev in {2, 4, 6, 8} and next == 10 - prev, however, 5 is not in visited. e.g. 2->8 and 5 not visited.

Code

class Solution(object):
    def numberOfPatterns(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        visited = {}
        self.res = 0
        self.corner = {1,3,7,9}
        self.mid = {2,4,6,8}
        for i in range(1, 10):
            visited[i] = 1
            self.dfsHelper(visited, 1, m, n, i)
            del visited[i]
        return self.res
        
    # 递归的定义：找出所有合理的next pos
    def dfsHelper(self, visited, keys, m, n, prev):
        # 递归的出口：
        if m <= keys <= n:
            self.res += 1
        if keys == n:
            return

        # 递归的拆解：对1-10遍历，找到valid的next
        for next in range(1, 10):
            if next not in visited:
                if prev in self.corner and next in self.corner and (prev + next)/2 not in visited:
                    continue
                elif prev in self.mid and next == (10 - prev) and 5 not in visited:
                    continue
                visited[next] = 1
                self.dfsHelper(visited, keys + 1, m, n, next)
                del visited[next]
                
#         self.corners = set([1, 3, 7, 9])
#         self.mids = set([2, 4, 6, 8])
#         visited = {}
#         self.res = 0
#         for i in range(1, 10):
#             visited[i] = 1
#             self.dfs(m, n, 1, i, visited)
#             del visited[i]
        
#         return self.res
    
#     # 递归的定义：找出所有合理的next pos
#     def dfs(self, lower, upper, visited_num, prev_n, visited):
#         # 递归的出口：
#         if lower <= visited_num <= upper:
#             self.res += 1
#         if visited_num > upper:
#             return

#         # 递归的拆解：对1-10遍历，找到valid的next
#         for next_n in range(1, 10):
#             if self.isValid(prev_n, next_n, visited):
#                 visited[next_n] = 1
#                 self.dfs(lower, upper, next_n, visited)
#                 del visited[next_n]
    
#     def isValid(self, prev_n, next_n, visited):
#         if prev_n != next_n:
#             if prev_n in self.corners and next_n in self.corners and (prev_n + next_n) / 2 in visited:
#                 return True
#             if prev_n in self.mids and next_n in self.mids and (prev_n + next_n) / 2 in visited:
#                 return True
#         return False