351. Android Unlock Patterns

发表于 | 分类于

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.
alt text
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.

解法1：

这题一拿到感觉是dp或者是dfs的题目。用dp想不出状态方程看来只能用dfs试一下。
dfs的话最核心的思想就是每次往目标前进一步，如果成功则再继续探寻。
这个问题的一部是要看上一步和当前一步是否构成一个合适的movement.
一定是：
１．　相邻的
２．　对线的
３．　不相邻但是当中的数字已经被访问过了

那么用一个数组维护访问过的数字，同时维护一个上次访问的数字和当前的数字，以便判断一个move是否合适。
对于每一个数字进行dfs遍历，每前进一步就把所剩的步数－１．
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
public class Solution {
    public int numberOfPatterns(int m, int n) {
        int sum = 0;
        for (int i = m; i <= n; i++) {
            boolean[] visited = new boolean[9]; // initialize the array
            sum += dfs(visited, -1, i);
        }
        return sum;
    }
    private boolean isValidMove(boolean[] visited, int last, int current) {
        if (visited[current]) {
            return false;
        }
        if (last == -1) {
            // First move, always true
            return true;
        }
        if ((last + current) % 2 == 1) {
            return true;
        }
        int row_last = last / 3;
        int row_current = current / 3;
        int col_last = last % 3;
        int col_current = current % 3;
//         if (row_last == row_current && (Math.abs(col_last - col_current) == 1)) {
//             return true;
//         }
//         if (col_last == col_current && (Math.abs(row_last - row_current) == 1)) {
//             return true;
//         }
        int mid = (last + current) / 2;
        if (mid == 4) {
            return visited[mid];    // diagonal
        }
        if (row_last != row_current && col_last != col_current) {
            return true;
        }
        return visited[mid];
    }
    private int dfs(boolean[] visited, int last, int len) {
        // last is the last visited number
        // len is the remaining length of required key string
        if (len == 0) {
            return 1;
        }
        // record the sum
        int sum = 0;
        for (int i = 0; i < 9; i++) {
            // Move from last to i
            if (isValidMove(visited, last, i)) {
                visited[i] = true;
                sum += dfs(visited, i, len - 1);
                visited[i] = false;
            }
        }
        return sum;
    }
}

解法2：

由于可能的跳跃是有限的，可以用一个table来存储合法的跳跃path。这样可以简化很多检查一个move是否合法的code。
每次DFS的时候从一个点开始，找出可能的path。同时利用对称性，1,3,7,9是一样的；2,4,6,8是一样的。5单独一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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;
    }
}