351. Android Unlock Patterns
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 any other dot, the other dot must have previously appeared in the sequence. No jumps through non-selected dots are allowed.
Here are some example valid and invalid unlock patterns:
- The 1st pattern
[4,1,3,6]
is invalid because the line connecting dots1
and3
pass through dot2
, but dot2
did not previously appear in the sequence. - The 2nd pattern
[4,1,9,2]
is invalid because the line connecting dots1
and9
pass through dot5
, but dot5
did not previously appear in the sequence. - The 3rd pattern
[2,4,1,3,6]
is valid because it follows the conditions. The line connecting dots1
and3
meets the condition because dot2
previously appeared in the sequence. - The 4th pattern
[6,5,4,1,9,2]
is valid because it follows the conditions. The line connecting dots1
and9
meets the condition because dot5
previously appeared in the sequence.
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
Rust Solution
struct Solution;
impl Solution {
fn number_of_patterns(m: i32, n: i32) -> i32 {
let mut res = 0;
let mut visited = vec![vec![false; 3]; 3];
Self::dfs(0, None, &mut visited, &mut res, m as usize, n as usize);
res as i32
}
fn dfs(
start: usize,
prev: Option<(usize, usize)>,
visited: &mut Vec<Vec<bool>>,
all: &mut usize,
m: usize,
n: usize,
) {
if start >= m {
*all += 1;
}
if start == n {
return;
}
if let Some((r, c)) = prev {
for i in 0..3 {
for j in 0..3 {
if !visited[i][j] {
if ((i == r && j + c == 2)
|| (j == c && i + r == 2)
|| (i + r == 2 && j + c == 2))
&& !visited[(i + r) / 2][(j + c) / 2]
{
continue;
}
visited[i][j] = true;
Self::dfs(start + 1, Some((i, j)), visited, all, m, n);
visited[i][j] = false;
}
}
}
} else {
for i in 0..3 {
for j in 0..3 {
visited[i][j] = true;
Self::dfs(start + 1, Some((i, j)), visited, all, m, n);
visited[i][j] = false;
}
}
}
}
}
#[test]
fn test() {
let m = 1;
let n = 1;
let res = 9;
assert_eq!(Solution::number_of_patterns(m, n), res);
let m = 1;
let n = 2;
let res = 65;
assert_eq!(Solution::number_of_patterns(m, n), res);
}
Having problems with this solution? Click here to submit an issue on github.