A smartphone's pattern lock screen consists of a 3×3 grid of dots numbered 1 through 9:
1 2 3 4 5 6 7 8 9
Users unlock their phone by connecting dots in sequence. A valid pattern must follow these rules:
Each dot can be visited at most once
When connecting two dots, if there's a dot directly between them (horizontally, vertically, or diagonally), that intermediate dot must have already been visited
The pattern must connect at least m dots and at most n dots
For example:
Moving from dot 1 to dot 3 requires dot 2 to have been visited first
Moving from dot 1 to dot 9 requires dot 5 to have been visited first
Moving from dot 1 to dot 5 is always allowed (no dot in between)
Calculate how many distinct valid patterns exist with lengths between m and n (inclusive).
Requirements
Count all valid unlock patterns with length between m and n dots
A dot cannot be used more than once in a pattern
Jumps over unvisited intermediate dots are invalid
The pattern length must be at least m and at most n
Constraints
1 ≤ m ≤ n ≤ 9
The grid is always 3×3
Return the total count as an integer
Examples
Example 1:
Input: m = 1, n = 1 Output: 9 Explanation: Any single dot forms a valid pattern of length 1. There are 9 dots total.
Example 2:
`
Input: m = 1, n = 2
Output: 65
Explanation:
9 patterns of length 1 (each individual dot)
56 patterns of length 2 (valid two-dot connections)