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

89 阅读 0 评论 59 点赞

我是靠谱客的博主怕孤独硬币，这篇文章主要介绍【C++实现】安卓手机锁屏手势密码种数【模拟+递归搜索】，现在分享给大家，希望可以做个参考。

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

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

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

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

根据规则编写递归代码：

复制代码

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

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

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

$2$ ：

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

$5$ ：

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

$22$ ：

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

代码：

复制代码

#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;
}

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#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;
}