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:
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.
Credits:
Special thanks to @elmirap for adding this problem and creating all test cases.
Analysis:
Use an matrix to store the corssed number for each possible move and use DFS to find out all patterns.
Solution:
1 public class Solution { 2 public int numberofPatternsRecur(boolean[] visited, int[][] skip, int cur, int curLen, int m, int n){ 3 if (curLen == n) return 1; 4 5 visited[cur] = true; 6 // If current pattern is longer than m, than count 1 pattern. 7 int totalNum = (curLen>=m) ? 1 : 0; 8 for (int i=1;i<=9;i++) 9 if (!visited[i] && visited[skip[cur][i]]){ 10 totalNum += numberofPatternsRecur(visited,skip,i,curLen+1,m,n); 11 } 12 13 visited[cur] = false; 14 return totalNum; 15 } 16 17 public int numberOfPatterns(int m, int n) { 18 if (n<m || n<=0 || m<0 ) return 0; 19 20 int[][] skip = new int[10][10]; 21 skip[1][3] = skip[3][1] = 2; 22 skip[1][7] = skip[7][1] = 4; 23 skip[3][9] = skip[9][3] = 6; 24 skip[7][9] = skip[9][7] = 8; 25 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; 26 boolean[] visited = new boolean[10]; 27 // This is important, as all move that does not cross any number will query this. 28 visited[0] = true; 29 int res = 0; 30 res += numberofPatternsRecur(visited,skip,1,1,m,n)*4; 31 res += numberofPatternsRecur(visited,skip,2,1,m,n)*4; 32 res += numberofPatternsRecur(visited,skip,5,1,m,n); 33 return res; 34 } 35 }
LeetCode-Android Unlock Patterns
原文：http://www.cnblogs.com/lishiblog/p/5752768.html