题目描述： 我们都知道安卓有个手势解锁的界面，是一个 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： 主要思路： （1）对于3*3的网格界面，当前位置可以跳到的位置是相邻的位置，或相隔一个键的位置； （2）跳到相邻的位置时，要求相邻位置没有被访问过即可； （3）跳到相隔一个键的位置，要求相隔的这个键被访问过，但要跳到的这个位置没有被访问过； （4）根据这个思路，定义两个数组，一个一维的数组visited用来标识访问过的位置，一个二维数组，使用当前位置和要跳到间隔位置，来查找相隔的中间键的值，使用该键值来确定该中间位置是否访问过； （5）然后从以1为起点，dfs搜索所有的满足要求的路径，记录数量，由于结构的对称性，以3,7,9为起点获得的路径的数量相同，故直接乘以4即可，同理对于以2为起点，获得路径数量，乘以4，表示其他的4,6,8三个位置为起点获得的路径数量，再以5为起点，获得路径数量，将上述三组数量相加，即为总的数量；
class Solution { public: int dfs(int m,int n,int begin,int len,int res,bool* visited,int jumps[][10]){ //路径长度至少为m，才满足要求，可以统计 if(len>=m) ++res; ++len;//长度自增 //长度大于n，表示不再满足要求 if(len>n) return res; //表示访问过的位置 visited[begin]=true; //搜索所有可能的位置 for(int i=1;i<10;++i){ //获得间隔的位置 int jump=jumps[begin][i]; //首先没被访问过，其次间隔为0，既相邻，或间隔的位置被访问过 if(!visited[i]&&(jump==0||visited[jump])) res=dfs(m,n,i,len,res,visited,jumps); } //复原 visited[begin]=false; return res; } int numberOfPatterns(int m, int n) { bool visited[10]={0};//表示是否访问过 int jumps[10][10]={10};//查询中间间隔位置 //初始化，获得各个间隔位置 jumps[1][3]=2; jumps[3][1]=2; jumps[4][6]=5; jumps[6][4]=5; jumps[7][9]=8; jumps[9][7]=8; jumps[1][7]=4; jumps[7][1]=4; jumps[2][8]=5; jumps[8][2]=5; jumps[3][9]=6; jumps[9][3]=6; jumps[1][9]=5; jumps[9][1]=5; jumps[3][7]=5; jumps[7][3]=5; int res=0; //将三组数量相加 res+=dfs(m,n,1,1,0,visited,jumps)*4; res+=dfs(m,n,2,1,0,visited,jumps)*4; res+=dfs(m,n,5,1,0,visited,jumps); return res; } };