莆田市商城网站建设/新东方英语线下培训学校

【C++实现】安卓手机锁屏手势密码种数【模拟+递归搜索】

题目：
计算出安卓手机上的解锁屏幕手势密码的种类数目
（正确答案：389112种）

需要考虑的实际情况：
1.用户最少划4个点作为手势密码
2.不考虑用户的误触，两点之间可以按“日”轨迹滑动
3.两点之间如果存在第三个点，这个第三个点一定被手势激活

思路：
主要利用模拟和递归搜索。
正确的规则如下：

根据规则编写递归代码：

参数说明：n: 代表手势点的个数count: 代表在n个手势点的情况下，合法的组合种数x,y: 代表当前状态下的手势点划到的位置
递归终止条件：当n==1时，说明手势点已经通过某条合法的路径划了n个点count++
递归执行逻辑：1.遍历所有手势点，找到没有访问过的手势点，进一步判断该手势点是否满足上述的正确规则；2.如果满足上述正确规则，则标记访问该手势点，递归，回溯

关于判断两点之间是否满足正确规则的方法：
核心：利用两点距离
通过分析可以发现，两点的距离从小到大包括：
$1$ 和$\sqrt{2}$ ：

所以当下一状态手势点和当前状态点的距离 dis ≤ $\sqrt{2}$ 时，说明两点之间一定不会存在第三点。可直接进入递归。

$2$ ：

当下一状态手势点和当前状态点的距离 dis = 2 时，说明两点之间一定会存在第三点，此时需要判断中间点是否访问过，如果访问过说明合法。方可进入递归。

$\sqrt{5}$ ：

所以当下一状态手势点和当前状态点的距离 dis = $\sqrt{5}$ 时，说明两点之间一定不会存在第三点。可直接进入递归。

$2\sqrt{2}$ ：

当下一状态手势点和当前状态点的距离 dis =$2\sqrt{2}$ 时，说明两点之间一定会存在第三点，此时需要判断中间点是否访问过，如果访问过说明合法。方可进入递归。

代码：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;bool visited[3][3];//代表当前某点是否已经访问过//n:代表手势点的个数
//count:代表合法的组合种数
//x,y:代表当前状态下的点位置
void dfs(int n, int& count, int x, int y) {if (n == 1) {count++;return;}for (int i = 0; i <=2 ; i++) {for (int j = 0; j <= 2; j++) {if (!visited[i][j]) {int a_square = (i - x)*(i - x);int b_square = (j - y)*(j - y);double dis = sqrt(a_square + b_square);//如果走没有访问过的相邻的点，说明合法if (dis <= sqrt(2)) {::visited[i][j] = true;dfs(n - 1, count, i, j);::visited[i][j] = false;}//如果跨一个点走横竖线，并且中间的节点是访问过的，说明合法else if (abs(dis - 2) <= 0.00001 && visited[(i+x)/2][(j+y)/2]) {::visited[i][j] = true;dfs(n - 1, count, i, j);::visited[i][j] = false;}//如果走没有访问过的日字，说明合法else if (abs(dis - sqrt(5)) <= 0.00001) {::visited[i][j] = true;dfs(n - 1, count, i, j);::visited[i][j] = false;}//如果跨一个点走斜线（如左上到右下），并且中间的节点是访问过的，说明合法else if (abs(dis - 2 * sqrt(2)) <= 0.00001&&visited[(i + x) / 2][(j + y) / 2]) {::visited[i][j] = true;dfs(n - 1, count, i, j);::visited[i][j] = false;}}}}
}int main() {int sum = 0;for (int n = 4; n <= 9; n++) {int count = 0;for (int x = 0; x <= 2; x++) {for (int y = 0; y <= 2; y++) {//初始化第一个落指的手势点memset(visited, 0, sizeof(visited));visited[x][y] = true;dfs(n, count, x, y);}}sum += count;cout << "手势点 = " << n << "有" << count << "种情况。"<<endl;}cout <<"所以一共有"<< sum <<"种情况。"<< endl;system("pause");return 0;
}

运行结果：

欢迎大佬们批评指正！一同交流分享更好的思路！

PS：欢迎关注公众号~
不间断分享大厂算法题解、实习面经、学习资料等。
文末防伪码：2020214053