• ㊗️
• 大家
• offer
• 多多！

## 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 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.

## Code

class Solution {
public int numberOfPatterns(int m, int n) {
int[][] skip = new int[10][10];
// 记录要跳过的情况
skip[1][3] = skip[3][1] = 2;
skip[1][7] = skip[7][1] = 4;
skip[3][9] = skip[9][3] = 6;
skip[7][9] = skip[9][7] = 8;

skip[1][9] = skip[9][1] = 5;
skip[2][8] = skip[8][2] = 5;
skip[3][7] = skip[7][3] = 5;
skip[4][6] = skip[6][4] = 5;

boolean[] visited = new boolean[10];
int res = 0;

for(int i = m; i <= n; i++){
// 1,3,7,9对称
// 已经用了一个点，所以要先i - 1
res += dfs(visited, skip, 1, i - 1) * 4;
// 2,4,6,8对称
res += dfs(visited, skip, 2, i - 1) * 4;
// 5
res += dfs(visited, skip, 5, i - 1);
}

return res;
}

// remain 还剩下几个点可以用
private int dfs(boolean[] visited, int[][] skip, int cur, int remain){
if(remain < 0) return 0;
if(remain == 0) return 1;

visited[cur] = true;
int res = 0;

for(int i = 1; i <= 9; i++){
// 节点还没有访问过 && (skip == 0表示相邻的点，不需要越过 ||
// visited[skip[cur][i]]需要跳过，但是需要用的中介点已经访问过了)
if(!visited[i] && (skip[cur][i] == 0 || visited[skip[cur][i]])){
res += dfs(visited, skip, i, remain - 1);
}
}

visited[cur] = false;
return res;
}
}