题目描述

我们都知道安卓有个手势解锁的界面，是一个 3 x 3 的点所绘制出来的网格。

给你两个整数，分别为 ​​m 和 n，其中 1 ≤ m ≤ n ≤ 9，那么请你统计一下有多少种解锁手势，是至少需要经过 m 个点，但是最多经过不超过 n 个点的。

先来了解下什么是一个有效的安卓解锁手势:

每一个解锁手势必须至少经过 m 个点、最多经过 n 个点。
解锁手势里不能设置经过重复的点。
假如手势中有两个点是顺序经过的，那么这两个点的手势轨迹之间是绝对不能跨过任何未被经过的点。
经过点的顺序不同则表示为不同的解锁手势。

解释:

| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
无效手势：4 - 1 - 3 - 6
连接点 1 和点 3 时经过了未被连接过的 2 号点。

无效手势：4 - 1 - 9 - 2
连接点 1 和点 9 时经过了未被连接过的 5 号点。

有效手势：2 - 4 - 1 - 3 - 6
连接点 1 和点 3 是有效的，因为虽然它经过了点 2 ，但是点 2 在该手势中之前已经被连过了。

有效手势：6 - 5 - 4 - 1 - 9 - 2
连接点 1 和点 9 是有效的，因为虽然它经过了按键 5 ，但是点 5 在该手势中之前已经被连过了。

样例

输入: m = 1，n = 1
输出: 9

算法1

dfs回溯

暴搜0-8

C++ 代码

class Solution {
public:
    int numberOfPatterns(int m, int n) {
        dfs(0, 1, m, n);
        dfs(1, 1, m, n);
        res *= 4;
        dfs(4, 1, m, n);
        return res;
    }
private:
    void dfs(int u, int cnt, int m, int n)
    {
        // base case
        if (cnt >= m && cnt <= n) res ++;
        if (cnt >= n) return;
        // recursion
        visited[u] = true;
        for (int v = 0; v < 9; v ++ )
            if (!visited[v])
            {
                int diffx = abs(u / 3 - v / 3), diffy = abs(u % 3 - v % 3);
                if (diffx <= 1 && diffy <= 1) 
                    dfs(v, cnt + 1, m, n);
                // 这个条件是真的没看出来 @ 是通过复制正确答案调试发现的
                else if ((u + v) % 2 != 0)
                    dfs(v, cnt + 1, m, n);
                else if (visited[(u + v) >> 1]) 
                    dfs(v, cnt + 1, m, n);
            }
        visited[u] = false;
    }
    int res = 0;
    bool visited[9] = {false};
};

算法2

并查集

整个范围也就3x3，所以可以初始化来合并那些不在相邻8格的点，然后再dfs

C++ 代码

class Solution {
public:
    int numberOfPatterns(int m, int n) {
        init();
        for(int i = 1; i < 10; ++ i) dfs(i, 1, m, n);
        return ans;
    }
void dfs(int node, int cnt, int m, int n){
        if(cnt > n) return;
        else if(cnt >= m && cnt <= n) ++ res;
        visited[node] = true;
        for(int i = 1; i < 10; ++ i){
            bool flag = find(node) == find(i);
            if(!visited[i] && (!flag || visited[(node + i) >> 1])) dfs(i, cnt + 1, m, n);
        }
        visited[node] = false;
    }
inline void init(){
        for(int i = 1; i < 10; ++ i) fa[i] = i;
        union_(1,3);
        union_(1,7);
        union_(1,9);
        union_(2,8);
        union_(4,6);
    }
    inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
    inline void union_(int x, int y){if(find(x)!=find(y)) fa[find(x)]=find(fa[y]);}
    int res = 0;
    bool visited[10] = {false};
    int fa[10];
};