351. 安卓系统手势解锁 （ dfs 回溯 ）_安卓系统手势解锁 回溯

LeetCode： 351. 安卓系统手势解锁

回溯 dfs 题

AC Code

class Solution {
    public int numberOfPatterns(int m, int n) {
        // 按键
        boolean[] vis = new boolean[10];
        // 键盘
        int[][] map = new int[10][10];
        //这个 map 数组是为了记录跳跃的点数，比如说从1到3，就跳跃2
        //而且因为是对称的操作，所以3到1也是如此
        map[1][3] = map[3][1] = 2;
        map[7][9] = map[9][7] = 8;
        map[1][7] = map[7][1] = 4;
        map[3][9] = map[9][3] = 6;
        map[4][6] = map[6][4] = map[1][9] = map[9][1] = 5;
        map[3][7] = map[7][3] = map[2][8] = map[8][2] = 5;

        int ans = 0;
        //深度遍历，遍历每一个点到点的次数
        for(int i = m; i <= n; i++){
            // 这么多点
            //因为从1,3,7,9出发都是对称的，为什么i要减一呢，因为我们是从1出发，先天少了一个节点
            ans += dfs(1, vis, map, i - 1) * 4;

            // 2 4 6 8 出发都是对称的
            ans += dfs(2, vis, map, i - 1) * 4;
            
            // 5 独立
            ans += dfs(5, vis, map, i - 1);
        }

        return ans;
    }

    public int dfs(int cur, boolean[] vis, int[][] map, int cnt){
        int ans = 0;
        if(cnt == 0) return 1;
        vis[cur] = true;

        for(int i = 1; i <= 9; i++){
         	//看当前的节点到i节点的路径中有没有其他节点在中间
            int skip = map[cur][i];
            if((skip == 0 || vis[skip]) && !vis[i]){
            //如果这一次我们的i节点没有被读过，那么就判断有没有路过中间节点(visited[crossThroughNumber])
            // 或者这两个节点相邻没有中间节点（currentThrough=0）
                ans += dfs(i, vis, map, cnt - 1);
            }
        }
        
        // 要返回上一层了， 回溯 
        vis[cur] = false;
        
        return ans;
    }

}

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