351. Android Unlock Patterns

Problem

Android devices have a special lock screen with a 3 x 3 grid of dots. Users can set an "unlock pattern" by connecting the dots in a specific sequence, forming a series of joined line segments where each segment's endpoints are two consecutive dots in the sequence. A sequence of k dots is a valid unlock pattern if both of the following are true:

• All the dots in the sequence are distinct.
• If the line segment connecting two consecutive dots in the sequence passes through the center of any other dot, the other dot must have previously appeared in the sequence. No jumps through non-selected dots are allowed.

Given two integers m and n, return the number of unique and valid unlock patterns of the Android grid lock screen that consist of at least m keys and at most n keys.

Two unlock patterns are considered unique if there is a dot in one sequence that is not in the other, or the order of the dots is different.

Example 1:

Input: m = 1, n = 1
Output: 9

Example 2:

Input: m = 1, n = 2
Output: 65

Constraints:

• 1 <= m, n <= 9

Solution Approach

• Backtracking. When sliding from one point to another on the 3x3 grid, if the move passes exactly through a third point in the middle (for example, 1->3 passes through 2, and 1->9 passes through 5), then that middle point must already have been selected; otherwise, the step is invalid.
• Use blocker[a][b] to record the middle point that must be passed through from a to b; 0 means the points are adjacent and no point needs to be crossed. Set a virtual starting point 0, from which we can move to any digit, then use DFS to count all valid paths whose lengths fall within [m, n].

Code

package leetcode

// blocker351[a][b] records the middle point that must be passed through when sliding from point a to point b; 0 means the two points are adjacent and no middle point is needed.
// For example, 1->3 must pass through 2 first, and 1->9 must pass through 5 first.
var blocker351 = [10][10]int{
	1: {3: 2, 7: 4, 9: 5},
	2: {8: 5},
	3: {1: 2, 7: 5, 9: 6},
	4: {6: 5},
	6: {4: 5},
	7: {1: 4, 3: 5, 9: 8},
	8: {2: 5},
	9: {1: 5, 3: 6, 7: 8},
}

// Solution 1: backtracking. Point 0 is a virtual starting point, from which we can move to any digit.
func numberOfPatterns(m int, n int) int {
	visited := make([]bool, 10)
	return countPatterns351(visited, 0, 0, m, n)
}

// now is the current point, already is the number of selected points, and this counts the number of valid patterns whose lengths fall within [m,n].
func countPatterns351(visited []bool, now, already, m, n int) int {
	res := 0
	if already >= m && already <= n {
		res++
	}
	if already >= n { // The maximum length has been reached, so no need to select further
		return res
	}
	for next := 1; next <= 9; next++ {
		mid := blocker351[now][next]
		// next has not been used, and next is adjacent to now (mid==0) or the middle point has already been passed through (visited[mid])
		if !visited[next] && (mid == 0 || visited[mid]) {
			visited[next] = true
			res += countPatterns351(visited, next, already+1, m, n)
			visited[next] = false
		}
	}
	return res
}