我们都知道安卓有个手势解锁的界面,是一个 3 x 3 的点所绘制出来的网格。
给你两个整数,分别为 m 和 n,其中 1 ≤ m ≤ n ≤ 9, 那么请你统计一下有多少种解锁手势,是至少需要经过 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
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/android-unlock-patterns 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
vector<bool> visited;
public:
int numberOfPatterns(int m, int n) {
int ans = 0;
for(int len = m; len <= n; ++len)
{
visited = vector<bool> (9, false);
ans += cal(-1,len);
}
return ans;
}
bool isok(int idx, int last)
{
if(visited[idx]) return false;
if(last == -1) return true;//第一个数
if((idx+last)%2 == 1) return true;//相邻的两个数
int mid = (idx+last)/2;
if(mid == 4)//对角线的两个端点要连起来
return visited[mid];//看中点是否占用
if(idx%3 != last%3 && idx/3 != last/3)
return true;//不是 同行,或者 同列 的两个端点
return visited[mid];//检查0,6,中间是3,有没有被占用
}
int cal(int last, int len)
{
if(len == 0) return 1;
int sum = 0;
for(int i = 0; i < 9; ++i)
{
if(isok(i, last))
{
visited[i] = true;
sum += cal(i, len-1);
visited[i] = false;
}
}
return sum;
}
};
296 ms 6.1 MB
1,9, 389497 5,9, 387488, 有38万多种手势。