Given an Android 3x3 key lock screen and two integers m and n, where 1 ≤ m ≤ n ≤ 9, count the total number of unlock patterns of the Android lock screen, which consist of minimum of m keys and maximum n keys.
Rules for a valid pattern:
Each pattern must connect at least m keys and at most n keys.
All the keys must be distinct.
If the line connecting two consecutive keys in the pattern passes through any other keys, the other keys must have previously selected in the pattern. No jumps through non selected key is allowed.
The order of keys used matters.
Explanation:
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
Invalid move: 4 - 1 - 3 - 6
Line 1 - 3 passes through key 2 which had not been selected in the pattern.
Invalid move: 4 - 1 - 9 - 2
Line 1 - 9 passes through key 5 which had not been selected in the pattern.
Valid move: 2 - 4 - 1 - 3 - 6
Line 1 - 3 is valid because it passes through key 2, which had been selected in the pattern
Valid move: 6 - 5 - 4 - 1 - 9 - 2
Line 1 - 9 is valid because it passes through key 5, which had been selected in the pattern.
Example:Given m = 1, n = 1, return 9.
一刷
題解：安卓機(jī)子的解鎖方法姐浮，有9個(gè)數(shù)字鍵箫柳，如果密碼的長度范圍在[m, n]之間是己，問所有的解鎖模式共有多少種，注意題目中給出的一些非法的滑動(dòng)模式。那么我們先來看一下哪些是非法的，首先1不能直接到3，必須經(jīng)過2，同理的有4到6记罚，7到9墅诡，1到7，2到8桐智，3到9末早，還有就是對(duì)角線必須經(jīng)過5，例如1到9说庭，3到7等然磷。我們建立一個(gè)二維數(shù)組jumps，用來記錄兩個(gè)數(shù)字鍵之間是否有中間鍵刊驴，然后再用一個(gè)一位數(shù)組visited來記錄某個(gè)鍵是否被訪問過姿搜，然后我們用遞歸來解，我們先對(duì)1調(diào)用遞歸函數(shù)捆憎，在遞歸函數(shù)中舅柜，我們遍歷1到9每個(gè)數(shù)字next，然后找他們之間是否有jump數(shù)字躲惰，如果next沒被訪問過致份，并且jump為0，或者jump被訪問過础拨，我們對(duì)next調(diào)用遞歸函數(shù)氮块。數(shù)字1的模式個(gè)數(shù)算出來后绍载，由于1,3,7,9是對(duì)稱的，所以我們乘4即可滔蝉，然后再對(duì)數(shù)字2調(diào)用遞歸函數(shù)击儡，2,4,6,9也是對(duì)稱的，再乘4锰提，最后單獨(dú)對(duì)5調(diào)用一次曙痘，然后把所有的加起來就是最終結(jié)果了。
public class Solution {
// cur: the current position
// remain: the steps remaining
int DFS(boolean vis[], int[][] skip, int cur, int remain) {
if(remain < 0) return 0;
if(remain == 0) return 1;
vis[cur] = true;
int rst = 0;
for(int i = 1; i <= 9; ++i) {
// If vis[i] is not visited and (two numbers are adjacent or skip number is already visited)
if(!vis[i] && (skip[cur][i] == 0 || (vis[skip[cur][i]]))) {
rst += DFS(vis, skip, i, remain - 1);
}
}
vis[cur] = false;
return rst;
}
public int numberOfPatterns(int m, int n) {
// Skip array represents number to skip between two pairs
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] = skip[2][8] = skip[8][2] = skip[3][7] = skip[7][3] = skip[4][6] = skip[6][4] = 5;
boolean vis[] = new boolean[10];
int rst = 0;
// DFS search each length from m to n
for(int i = m; i <= n; ++i) {
rst += DFS(vis, skip, 1, i - 1) * 4; // 1, 3, 7, 9 are symmetric
rst += DFS(vis, skip, 2, i - 1) * 4; // 2, 4, 6, 8 are symmetric
rst += DFS(vis, skip, 5, i - 1); // 5
}
return rst;
}
}
二刷
另一種寫法立肘，同樣是DFS+backtracking
class Solution {
public int numberOfPatterns(int m, int n) {
boolean[] visited = new boolean[10];
visited[0] = true;
int[][] jumps = new int[10][10];
jumps[1][3] = jumps[3][1] = 2;
jumps[1][7] = jumps[7][1] = 4;
jumps[7][9] = jumps[9][7] = 8;
jumps[9][3] = jumps[3][9] = 6;
jumps[4][6] = jumps[6][4] = jumps[2][8] = jumps[8][2] = jumps[1][9] = jumps[9][1] = jumps[3][7] = jumps[7][3] = 5;
int count = 0;
count += 4 * dfs(1, 1, 0, m, n, visited, jumps);
count += 4 * dfs(2, 1, 0, m, n, visited, jumps);
count += dfs(5, 1, 0, m, n, visited, jumps);
return count;
}
private int dfs(int num, int len, int count, int m, int n, boolean[] visited, int[][] jumps) {
if (len >= m) count++;
len++;
if (len > n) return count;
visited[num] = true;
for (int next = 1; next <= 9; next++) {
if (!visited[next] && (jumps[num][next] == 0 || visited[jumps[num][next]])) {
count = dfs(next, len, count, m, n, visited, jumps);
}
}
visited[num] = false;
return count;
}
}
