安卓图案解锁

admin管理员组

文章数量:1516870

安卓图案解锁

链接：
来源：牛客网
 

栗主席(lizi)是某xxxx大学的一个不得了的程序猿，然而没想到吧，他竟然有女盆友，我们假设为QAQ！！！

那天，QAQ问栗子：你的小米5s的图像解锁密码到底是多少？

栗子：嘛？我仔细想想...   

QAQ：你仿佛在逗我...

...

栗子：我的图像解锁用过好多次密码，后来都是用指纹解锁，所以忘记密码辣。但是我记得可能是那几个密码

QAQ：那你务必告诉我...

栗子: ...

 

然后，栗子就写下了一堆可能的密码，安卓图案解锁中，数字对应的位置已经标出。

但是栗子当然不想把真正的密码告诉QAQ，所以给QAQ的一系列的密码中，甚至有一些密码，是不符合安卓图案解锁的规则的。

QAQ也知道栗子肯定不老实，给了很多错的密码，甚至不符合规则的密码，所以想请你来找出，哪些密码是不符合规则的。

链接：
来源：牛客网
 

安卓图案解锁的密码有这样的一些特点：

1.每个数字最多只会被使用一次。

2.如果想直接连接两个数字，但是线段中会经过另一个数字，当且仅有那个数字已经在之前就被使用过了，才会合法。(比如你想从1直接连接到9，那么要么是1->3->9,要么是3在之前已经被使用过了，然后才能直接从1->9)

输入描述:

多组输入
每组输入占一行，包含一串数字(1~9)，长度不超过30

输出描述:

输出这个安卓图案解锁是否合法，如果合法输出"YES",反之输出"NO" (请参照样例输出，不要输出引号)

示例1

输入

14569
1953
15963
15953

输出

YES
NO
YES
NO

题解：1 -> 3 是必须经过 2 的，1 -> 6 与 1 -> 8 是可以直达的，根据字符串模拟路径，没走完一个，将该点标记（标记作用：该点走过不能重复走；1 要走到 3 必须 2 要标记了）。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
int v[10],flag;
int leap[10][10];
void init(){leap[1][3]=leap[3][1]=2;leap[4][6]=leap[6][4]=5;leap[7][9]=leap[9][7]=8;leap[1][7]=leap[7][1]=4;leap[2][8]=leap[8][2]=5;leap[3][9]=leap[9][3]=6;leap[1][9]=leap[9][1]=leap[3][7]=leap[7][3]=5;
}int main(){string str;init();while(cin>>str){memset(v,0,sizeof(v));int len=str.length();if(!len){printf("NO\n");continue;}flag=false; int x=str[0]-'0';v[x]=1;for(int i=1;i<len;i++){int y=str[i]-'0';if(v[y]) { flag=true; break;}if(!leap[x][y]){x=y; v[y]=1;}else{if(v[leap[x][y]]) { x=y; v[y]=1; }else{flag=true;break;}}}if(flag) printf("NO\n");else printf("YES\n");}return 0;
}

 

351. 安卓系统手势解锁

我们都知道安卓有个手势解锁的界面，是一个 3 x 3 的点所绘制出来的网格。

给你两个整数，分别为 ​​m 和 n，其中 1 ≤ m ≤ n ≤ 9，那么请你统计一下有多少种解锁手势，是至少需要经过 m 个点，但是最多经过不超过 n 个点的。

先来了解下什么是一个有效的安卓解锁手势:

每一个解锁手势必须至少经过 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）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：从每个点出发，dfs搜索即可；可优化，从0开始与从3、7、9开始的对称，从2开始的与从4、6、8开始的对称

class Solution {
public:int v[10],sum=0;int temp[10][10];void init(){temp[1][3]=temp[3][1]=2;temp[4][6]=temp[6][4]=5;temp[7][9]=temp[9][7]=8;temp[1][7]=temp[7][1]=4;temp[2][8]=temp[8][2]=5;temp[3][9]=temp[9][3]=6;temp[1][9]=temp[9][1]=temp[3][7]=temp[7][3]=5;}void dfs(int x,int num,int n,int m){if(num>n) return ;if(m<=num&&num<=n) sum++;for(int i=1;i<=9;i++){if(i==x||v[i]||(temp[x][i]&&!v[temp[x][i]])) continue;v[i]=1; num++;dfs(i,num,n,m);v[i]=0; num--;}}int numberOfPatterns(int m, int n) {init();int ans=0;memset(v,0,sizeof(v)); sum=0; v[1]=1;dfs(1,1,n,m); ans+=sum*4;memset(v,0,sizeof(v)); sum=0; v[2]=1;dfs(2,1,n,m); ans+=sum*4;memset(v,0,sizeof(v)); sum=0; v[5]=1;dfs(5,1,n,m); ans+=sum;return ans;}
};

 

本文标签： 安卓图案解锁