|
| 1 | +/** |
| 2 | + * Given an Android 3x3 key lock screen and two integers m and n, where |
| 3 | + * 1 ≤ m ≤ n ≤ 9, count the total number of unlock patterns of the Android |
| 4 | + * lock screen, which consist of minimum of m keys and maximum n keys. |
| 5 | + * |
| 6 | + * Rules for a valid pattern: |
| 7 | + * - Each pattern must connect at least m keys and at most n keys. |
| 8 | + * - All the keys must be distinct. |
| 9 | + * - If the line connecting two consecutive keys in the pattern passes through |
| 10 | + * any other keys, the other keys must have previously selected in the pattern. |
| 11 | + * No jumps through non selected key is allowed. |
| 12 | + * - The order of keys used matters. |
| 13 | + * |
| 14 | + * Explanation: |
| 15 | + * | 1 | 2 | 3 | |
| 16 | + * | 4 | 5 | 6 | |
| 17 | + * | 7 | 8 | 9 | |
| 18 | + * Invalid move: 4 - 1 - 3 - 6 |
| 19 | + * Line 1 - 3 passes through key 2 which had not been selected in the pattern. |
| 20 | + * |
| 21 | + * Invalid move: 4 - 1 - 9 - 2 |
| 22 | + * Line 1 - 9 passes through key 5 which had not been selected in the pattern. |
| 23 | + * |
| 24 | + * Valid move: 2 - 4 - 1 - 3 - 6 |
| 25 | + * Line 1 - 3 is valid because it passes through key 2, which had been selected in the pattern |
| 26 | + * |
| 27 | + * Valid move: 6 - 5 - 4 - 1 - 9 - 2 |
| 28 | + * Line 1 - 9 is valid because it passes through key 5, which had been selected in the pattern. |
| 29 | + * |
| 30 | + * Example: |
| 31 | + * Given m = 1, n = 1, return 9. |
| 32 | + */ |
| 33 | + |
| 34 | +public class AndroidUnlockPatterns351 { |
| 35 | + private int[][] points = new int[][]{{0,0}, {0,1}, {0,2}, {1,0}, {1,1}, {1,2}, {2,0}, {2,1}, {2,2}}; |
| 36 | + |
| 37 | + public int numberOfPatterns(int m, int n) { |
| 38 | + boolean[][] visited = new boolean[3][3]; |
| 39 | + // corner |
| 40 | + int[] res0 = new int[1]; |
| 41 | + dfs(visited, 0, 0, m, n, 1, res0); |
| 42 | + |
| 43 | + // edge |
| 44 | + int[] res1 = new int[1]; |
| 45 | + dfs(visited, 0, 1, m, n, 1, res1); |
| 46 | + |
| 47 | + // center |
| 48 | + int[] res2 = new int[1]; |
| 49 | + dfs(visited, 1, 1, m, n, 1, res2); |
| 50 | + |
| 51 | + return res0[0] * 4 + res1[0] * 4 + res2[0]; |
| 52 | + } |
| 53 | + |
| 54 | + |
| 55 | + private void dfs(boolean[][] visited, int i, int j, int m, int n, int level, int[] res) { |
| 56 | + if (level > n) return; |
| 57 | + if (level >= m && level <=n) res[0]++; |
| 58 | + visited[i][j] = true; |
| 59 | + for (int[] p: points) { |
| 60 | + if (!visited[p[0]][p[1]] && canGo(i, j, p[0], p[1], visited)) { |
| 61 | + dfs(visited, p[0], p[1], m, n, level+1, res); |
| 62 | + } |
| 63 | + } |
| 64 | + visited[i][j] = false; |
| 65 | + } |
| 66 | + |
| 67 | + private boolean canGo(int i1, int j1, int i2, int j2, boolean[][] visited) { |
| 68 | + if (!isJumping(i1, j1, i2, j2)) return true; |
| 69 | + return visited[(i1+i2)/2][(j1+j2)/2]; |
| 70 | + } |
| 71 | + |
| 72 | + private boolean isJumping(int i1, int j1, int i2, int j2) { |
| 73 | + return (i1 == i2 && Math.abs(j1-j2) == 2) || |
| 74 | + (j1 == j2 && Math.abs(i1-i2) == 2) || |
| 75 | + (Math.abs(i1-i2) == 2 && Math.abs(j1-j2) == 2); |
| 76 | + } |
| 77 | + |
| 78 | + |
| 79 | + // cur: the current position |
| 80 | + // remain: the steps remaining |
| 81 | + int DFS(boolean vis[], int[][] skip, int cur, int remain) { |
| 82 | + if(remain < 0) return 0; |
| 83 | + if(remain == 0) return 1; |
| 84 | + vis[cur] = true; |
| 85 | + int rst = 0; |
| 86 | + for(int i = 1; i <= 9; ++i) { |
| 87 | + // If vis[i] is not visited and (two numbers are adjacent or skip number is already visited) |
| 88 | + if(!vis[i] && (skip[cur][i] == 0 || (vis[skip[cur][i]]))) { |
| 89 | + rst += DFS(vis, skip, i, remain - 1); |
| 90 | + } |
| 91 | + } |
| 92 | + vis[cur] = false; |
| 93 | + return rst; |
| 94 | + } |
| 95 | + |
| 96 | + public int numberOfPatterns2(int m, int n) { |
| 97 | + // Skip array represents number to skip between two pairs |
| 98 | + int skip[][] = new int[10][10]; |
| 99 | + skip[1][3] = skip[3][1] = 2; |
| 100 | + skip[1][7] = skip[7][1] = 4; |
| 101 | + skip[3][9] = skip[9][3] = 6; |
| 102 | + skip[7][9] = skip[9][7] = 8; |
| 103 | + 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; |
| 104 | + boolean vis[] = new boolean[10]; |
| 105 | + int rst = 0; |
| 106 | + // DFS search each length from m to n |
| 107 | + for(int i = m; i <= n; ++i) { |
| 108 | + rst += DFS(vis, skip, 1, i - 1) * 4; // 1, 3, 7, 9 are symmetric |
| 109 | + rst += DFS(vis, skip, 2, i - 1) * 4; // 2, 4, 6, 8 are symmetric |
| 110 | + rst += DFS(vis, skip, 5, i - 1); // 5 |
| 111 | + } |
| 112 | + return rst; |
| 113 | + } |
| 114 | + |
| 115 | +} |
0 commit comments