链接:https://ac.nowcoder.com/acm/problem/13585
来源:牛客网

题目描述
栗主席(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、7、9无法直接相连;4、6无法直接相连;2、8无法直接相连
    我们可以为这九个数字再定义一个数组,其中,颜色相同的用相等的值赋值,不等的用不同的值。于是,便可根据值是否相等以及点是否被使用过来判断是否合法。
  • 代码:*
    #include<iostream>
    #include<string.h>
    using namespace std;
    int main() {
       int a[9], b[9] = {1,2,1,3,0,3,1,2,1};
       string c;
       while (cin >> c) {
           int pt = 1;
           memset(a,0,sizeof(a));
           for (int i = 0; i < c.size()-1; i++) {
               int a1 = c[i] - '0';
               int a2 = c[i + 1] - '0';
               if (a1==a2){
                   pt = 0;
                   break;
               }
               if (a[a1 - 1]==1 || a[a2 - 1]==1) {
                   pt = 0;
                   break;
               }
               a[a1 - 1] = 1;
               if(b[a1 - 1]==b[a2 - 1] && !a[(a1+a2)/2-1]) {
                   pt = 0;
                   break;
               }
           }
           if (pt)
               cout << "YES" << endl;
           else cout << "NO" << endl;
       }
    }