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`

`n`

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 = 1Output:9

**Example 2:**

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

**Constraints:**

`1 <= m, n <= 9`

```
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);
}
```