模拟题之安卓图案解锁

https://ac.nowcoder.com/acm/contest/20960/1005

来源：牛客网

题目描述

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

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

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

QAQ：你仿佛在逗我...

...

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

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

栗子: ...

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

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

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

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

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

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

输入描述:

多组输入

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

输出描述:

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

示例1

输入

复制

14569

1953

15963

15953

输出

复制

YES

NO

YES

NO

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
//创建图案矩阵
int a[4][4] = {{1,2,3},{4,5,6},{7,8,9}};
pair<int, int> p[10];
int main() {
    p[1].first = 0;p[1].second = 0;
    p[2].first = 0;p[2].second = 1;
    p[3].first = 0;p[3].second = 2;
    p[4].first = 1;p[4].second = 0;
    p[5].first = 1;p[5].second = 1;
    p[6].first = 1;p[6].second = 2;
    p[7].first = 2;p[7].second = 0;
    p[8].first = 2;p[8].second = 1;
    p[9].first = 2;p[9].second = 2;
    //使用数组记录某个数字被使用的个数
    int used[11] = {};
    string s;
    bool flag;
    //策略是读一检测一
    while (cin>>s) {
        flag = true;
        fill(used, used+11, 0);
        //遍历
        for (int i=0;i<s.size();i++) {
            if (used[s[i]-'0']==0) {
                int x = p[s[i]-'0'].first;
                int y = p[s[i]-'0'].second;
                used[s[i]-'0'] += 1;
                //其中一个的x或y的值与前面的差大于1，并且差的减的结果等于2或0
                if (i!=0&&(abs(x-p[s[i-1]-'0'].first)>1||abs(y-p[s[i-1]-'0'].second)>1)&&abs(abs(x-p[s[i-1]-'0'].first)-abs(y-p[s[i-1]-'0'].second))!=1) {
                    //计算中间的坐标
                    int mid_x = (x+p[s[i-1]-'0'].first)/2, mid_y = (y+p[s[i-1]-'0'].second)/2;
                    if (used[a[mid_x][mid_y]]!=1) {
                        cout<<"NO\n";
                        flag = false;
                        break;
                    }
                }
            } else {
                cout<<"NO\n";
                flag = false;
                break;
            }
        }
        if (flag) {
            cout<<"YES\n";
        }
    }
    
    
    return 0;
}