[LeetCode] Android Unlock Patterns 安卓解锁模式

Given an Android 3x3 key lock screen and two integers m and n, where 1 ≤ m ≤ n ≤ 9, count the total number of unlock patterns of the Android lock screen, which consist of minimum of m keys and maximum n keys.

Rules for a valid pattern:

1. Each pattern must connect at least m keys and at most n keys.
2. All the keys must be distinct.
3. If the line connecting two consecutive keys in the pattern passes through any other keys, the other keys must have previously selected in the pattern. No jumps through non selected key is allowed.
4. The order of keys used matters.

Explanation:

| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |

Invalid move: 4 - 1 - 3 - 6

Line 1 - 3 passes through key 2 which had not been selected in the pattern.

Invalid move: 4 - 1 - 9 - 2
Line 1 - 9 passes through key 5 which had not been selected in the pattern.

Valid move: 2 - 4 - 1 - 3 - 6
Line 1 - 3 is valid because it passes through key 2, which had been selected in the pattern

Valid move: 6 - 5 - 4 - 1 - 9 - 2
Line 1 - 9 is valid because it passes through key 5, which had been selected in the pattern.

Example:
Given m = 1, n = 1, return 9.

Credits:
Special thanks to @elmirap for adding this problem and creating all test cases.

class Solution {
public:
int numberOfPatterns(int m, int n) {
int res = 0;
vector<bool> visited(10, false);
vector<vector<int>> jumps(10, vector<int>(10, 0));
jumps[1][3] = jumps[3][1] = 2;
jumps[4][6] = jumps[6][4] = 5;
jumps[7][9] = jumps[9][7] = 8;
jumps[1][7] = jumps[7][1] = 4;
jumps[2][8] = jumps[8][2] = 5;
jumps[3][9] = jumps[9][3] = 6;
jumps[1][9] = jumps[9][1] = jumps[3][7] = jumps[7][3] = 5;
res += helper(1, 1, 0, m, n, jumps, visited) * 4;
res += helper(2, 1, 0, m, n, jumps, visited) * 4;
res += helper(5, 1, 0, m, n, jumps, visited);
return res;
}
int helper(int num, int len, int res, int m, int n, vector<vector<int>> &jumps, vector<bool> &visited) {
if (len >= m) ++res;
++len;
if (len > n) return res;
visited[num] = true;
for (int next = 1; next <= 9; ++next) {
int jump = jumps[num][next];
if (!visited[next] && (jump == 0 || visited[jump])) {
res = helper(next, len, res, m, n, jumps, visited);
}
}
visited[num] = false;
return res;
}
}; 

class Solution {
public:
int numberOfPatterns(int m, int n) {
return count(m, n, 0, 1, 1);
}
int count(int m, int n, int used, int i1, int j1) {
int res = m <= 0;
if (!n) return 1;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
int I = i1 + i, J = j1 + j, used2 = used | (1 << (i * 3 + j));
if (used2 > used && (I % 2 || J % 2 || used2 & (1 << (I / 2 * 3 + J / 2)))) {
res += count(m - 1, n - 1, used2, i, j);
}
}
}
return res;
}
};

|
4月前
|

|
4月前
|
Android开发
Android Mediatek 增加Recovery模式下读cmdline的强制工厂重置选项
Android Mediatek 增加Recovery模式下读cmdline的强制工厂重置选项
46 0
|
23天前
|

Android经典实战之Kotlin委托模式和by关键字

41 4
|
3月前
|

Android Jetpack是谷歌为简化和优化安卓应用开发而推出的一套高级组件库。本文深入探讨了Jetpack的主要构成及其在应用开发中的实际运用，展示了如何通过使用这些工具来提升开发效率和应用性能。
79 0
|
22天前
|
Android开发

24 1
|
1月前
|
Java 网络安全 开发工具
UNITY与安卓⭐一、Android Studio初始设置
UNITY与安卓⭐一、Android Studio初始设置
34 2
|
2月前
|

Android Kotlin中使用 LiveData、ViewModel快速实现MVVM模式

136 2
|
3月前
|

【Android】安卓开发的前景
【Android】安卓开发的前景
78 1
|
4月前
|
Android开发 异构计算 前端开发
Android显示原理，安卓自定义view面试
Android显示原理，安卓自定义view面试
38 1
|
4月前
|

55 1