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

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

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

/*
1. 搜索顺序: 把当前点加入buffer,  达到最大深度跳出, 否则递归处理所有可能的点
2. 搜索状态: local: cur, status, depth | galbal:buffer, set
3. 剪枝: ~
4. 偏移为 0~8 处理, 剪枝跳出时回收状态
*/

class Solution {


    StringBuilder buffer = new StringBuilder();
    static final int BASE = 9;
    HashSet[] sets = new HashSet[BASE+1];

    public int numberOfPatterns(int m, int n) {
        int res = 0;

        for (int i = m ; i <= n ; i++) sets[i] = new HashSet<String>();

        res += start(0, m, n) * 4;
        res += start(1, m, n) * 4;
        res += start(4, m, n);

        return res;
    }

    public int start(int cur, int m, int n){
        int res = 0;
        for (int i = m ; i <= n ; i++) sets[i].clear();
        buffer.setLength(0);
        dfs(cur, set(0, cur), 1, m, n);
        for (int i = m ; i <= n ; i++) res += sets[i].size();
        return res;
    }

    void dfs(int cur, int status, int depth, int n, int m){
        buffer.append(cur);
        int len = buffer.length();
        if (n <= len && len <= m) sets[len].add(buffer.toString());
        if (len > m){
            // 跳出时回收状态
            buffer.setLength(len -1);
            return ;
        }

        for (int i = 0 ; i < BASE ; i ++){
            if (((status>> i) & 1) == 1) continue;
            if (check(cur, i, status))  dfs(i, set(status, i), depth + 1, n , m);
        }
        buffer.setLength(buffer.length() -1);
    }

    boolean check(int cur, int next, int status){

        int cx = cur / 3 ;
        int cy = cur % 3 ;
        int nx = next / 3;
        int ny = next % 3;

        int dx = Math.abs(cx - nx);
        int dy = Math.abs(cy - ny);

        if (dx == 2 && dy == 0  || dx == 0 && dy == 2) {
            int x =  cx + nx  >> 1;
            int y = cy + ny >> 1;
            return exist(status, 3 * x + y) ;
        }
        if (dx == 2 && dy == 2) return exist(status, 4);

        return true;
    }

    int set(int status, int index){
        return status | 1 << index;
    }

    boolean exist(int status, int index){
        return ((status >> index) & 1) == 1;
    }

}