数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 实现 Android 解锁图案
假设我们有一个 Android 3x3 键锁屏和两个整数 m 和 n，m 和 n 的值范围在 1 ≤ m ≤ n ≤ 9 之间。我们需要计算 Android 锁屏解锁图案的总数，这些图案至少包含 m 个键，最多包含 n 个键。
规则如下：每个图案必须连接至少 m 个键，最多 n 个键。所有键必须是唯一的。如果连接图案中两个连续键的线穿过任何其他键，则其他键必须已在图案中被选中。不允许跳过任何未选中的键。使用的键的顺序很重要。
因此，如果输入为 m = 1，n = 1，则输出将为 9
为了解决这个问题，我们将遵循以下步骤：
定义一个大小为 10 x 10 的数组 skip。
定义一个函数 dfs()，它将接收节点、长度和一个数组 visited 作为参数。
如果长度等于 0，则：
返回 1
将 visited[node] 设置为 true
ret := 0
从 i := 1 开始，当 i <= 9 时，更新（i 增加 1），执行：
如果 visited[i] 为 false 且 (skip[node, i] 等于 0 或 visited[skip[node, i]] 不为零)，则：
ret := ret + dfs(i, len - 1, visited)
将 visited[node] 设置为 false
返回 ret
从主方法执行以下操作：
用 0 填充 skip
skip[1, 3] := skip[3, 1] := 2
skip[1, 7] := skip[7, 1] := 4
skip[3, 9] := skip[9, 3] := 6
skip[7, 9] := skip[9, 7] := 8
skip[4, 6] := skip[6, 4] := skip[2, 8] := skip[8, 2] := skip[3, 7] := skip[7, 3] := skip[1, 9] := skip[9, 1] := 5
定义一个大小为 10 的数组 visited
ret := 0
从 i := m 开始，当 i <= n 时，更新（i 增加 1），执行：
ret := ret + (dfs(1, i - 1, visited))
ret := ret + (dfs(2, i - 1, visited))
ret := ret + dfs(5, i - 1, visited)
返回 ret
示例
让我们看下面的实现来更好地理解：
#include <bits/stdc++.h> using namespace std; class Solution { public: int skip[10][10]; int dfs(int node, int len, vector<bool>& visited){ if (len == 0) return 1; visited[node] = true; int ret = 0; for (int i = 1; i <= 9; i++) { if (!visited[i] && (skip[node][i] == 0 || visited[skip[node][i]])) { ret += dfs(i, len - 1, visited); } } visited[node] = false; return ret; } int numberOfPatterns(int m, int n){ memset(skip, 0, sizeof(skip)); skip[1][3] = skip[3][1] = 2; skip[1][7] = skip[7][1] = 4; skip[3][9] = skip[9][3] = 6; skip[7][9] = skip[9][7] = 8; skip[4][6] = skip[6][4] = skip[2][8] = skip[8][2] = skip[3][7] = skip[7][3] = skip[1][9] = skip[9][1] = 5; vector<bool> visited(10); int ret = 0; for (int i = m; i <= n; i++) { ret += (dfs(1, i - 1, visited) * 4); ret += (dfs(2, i - 1, visited) * 4); ret += dfs(5, i - 1, visited); } return ret; } }; main(){ Solution ob; cout << (ob.numberOfPatterns(1,1)); }
输入
1, 1
Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.
输出
9
1K+ 浏览量
