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 dots 1 and 3 pass through dot 2, but dot 2 did not previously appear in the sequence.
  • The 2nd pattern [4,1,9,2] is invalid because the line connecting dots 1 and 9 pass through dot 5, but dot 5 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 dots 1 and 3 meets the condition because dot 2 previously appeared in the sequence.
  • The 4th pattern [6,5,4,1,9,2] is valid because it follows the conditions. The line connecting dots 1 and 9 meets the condition because dot 5 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

351. Android Unlock Patterns
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);
}