NC13585 安卓图案解锁

题目描述
栗主席(lizi)是某xxxx大学的一个不得了的程序猿，然而没想到吧，他竟然有女盆友，我们假设为QAQ！！！
那天，QAQ问栗子：你的小米5s的图像解锁密码到底是多少？
栗子：嘛？我仔细想想…
QAQ：你仿佛在逗我…
…
栗子：我的图像解锁用过好多次密码，后来都是用指纹解锁，所以忘记密码辣。但是我记得可能是那几个密码
QAQ：那你务必告诉我…
栗子: …

然后，栗子就写下了一堆可能的密码，安卓图案解锁中，数字对应的位置已经标出。
但是栗子当然不想把真正的密码告诉QAQ，所以给QAQ的一系列的密码中，甚至有一些密码，是不符合安卓图案解锁的规则的。
QAQ也知道栗子肯定不老实，给了很多错的密码，甚至不符合规则的密码，所以想请你来找出，哪些密码是不符合规则的。
思路：
一条边有如下三种正确的情况：

1. 相邻
2. 横穿了某个点且这个点之前到达过
3. 不相邻，也不横穿某个点
   除此之外其他的边都是不合法的。
   本题中出现了三个数组。

mp表示每个格子的编号。
g表示两个点是否相邻
G表示两个点间横穿的点，若两个点之间不横穿其他点，那么G设置为0
题目链接：https://ac.nowcoder.com/acm/problem/13585
代码：

#include
#include
#include
#include
using namespace std;
bitset<10>g[10];
int G[10][10];
int mp[3][3];
int dx[]={1,-1,0,0,-1,1,-1,1},dy[]={0,0,1,-1,-1,1,1,-1};
int main()
{
    string str;
    int cnt=0;
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            mp[i][j]=++cnt;
        }
    }
    G[1][3]=2,G[3][1]=2,G[3][9]=6,G[9][3]=6,G[7][9]=8,G[9][7]=8,G[1][7]=4,G[7][1]=4,G[1][9]=5,G[9][1]=5,G[2][8]=5,G[8][2]=5,G[3][7]=5,G[7][3]=5,G[4][6]=5,G[6][4]=5;
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            for(int k=0;k<4;k++)
            {
                int a=i+dx[k];
                int b=j+dy[k];
                if(a>=0 && a<3 && b>=0 && b<3)
                {
                    int x=mp[i][j];
                    int y=mp[a][b];
                    g[x][y]=true;
                    g[y][x]=true;
                }
            }
        }
    }
    while(cin>>str)
    {
        bool st[10];
        memset(st,0,sizeof st);
        bool flag=1;
        st[str[0]-'0']=1;
        for(int i=1;i<str.size();i++)
        {
            int a=str[i-1]-'0';
            int b=str[i]-'0';
            if(st[b])
            {
                cout<<"NO"<<endl;
                flag=0;
                break;
            }
            st[b]=1;
           	if(g[a][b]) //相邻 
           	{
           		continue;
			}
			if(st[G[a][b]] && G[a][b])// 穿过 
			{
				continue;
			}
			if(!G[a][b]) //中间不经过其他点 
			{
				continue;
			}
			cout<<"NO"<<endl;
            flag=0;
            break;
        }
        if(flag)
        {
            cout<<"YES"<<endl;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78