[原创]HDU 5641 国王的手机 king’s phone

2016-03-12 21:22:58 Tabris_ 阅读数：644

博客爬取于2020-06-14 22:44:51
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/50867690

King’s Phone Accepts: 629 Submissions: 2980
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
问题描述
阅兵式上，国王见到了很多新奇东西，包括一台安卓手机。他很快对手机的图形解锁产生了兴趣。

解锁界面是一个 3 \times 33×3 的正方形点阵，第一行的三个点标号 1, 2, 31,2,3，第二行的三个点标号 4, 5, 64,5,6，第三行的三个点标号 7, 8, 97,8,9。密码本身是一段序列，表示经过点的先后顺序，但遵循如下规则：

  1. 密码至少经过四个点。

  2. 不能重复经过同一个点。

  3. 路径上的中间点不能跳过，除非已经被经过（34273427 是合法的，但 37243724 不合法）。

他想设置的密码的长度为正整数 k(1\le k\le 9)k(1≤k≤9)，密码序列为 s_1 s_2…s_k(0<=s_i < INT MAX) s 1 s 2…s k(0≤ s < int_max)，

他想知道这个密码序列是否合法，这个问题交给了你。
输入描述
第一行一个整数表示测试组数：T (0 < T ≤100000) 。

每组数据占一行，每行第一个数 kk，设置密码的长度；接着 kk 个正整数，之间用空格隔开，表示密码序列 s_1s_2…s_ks 1 s 2 …s k
。
输出描述
共 TT 行。对每组数据，若合法输出 valid，否则输出 invalid。

输入样例

3
4 1 3 6 2
4 6 2 1 3
4 8 1 6 7

输出样例

invalid
valid
valid

Hint
对于第一组数据，11 到 33 跳过了路径上的点 22，所以不合法。

对于第二组数据，11 到 33 时点 22 已经被经过了，所以合法。

对于第三组数据，8-> 1-> 6 -> 7
8→1→6→7 路径均没有中间点，所以合法。

本题主要是对不可能成立的判断

比如说 1->3是不可以的 因为中间会经过2
这样的有共有16种
one 与other 是两头的数 mid是中间的数 one->other时 如果mid没有被经过就是错误的 用数组标记一下就能判断有没有背经过
当然 我这个是单向的 如果双向的话会省一半
| one | other | mid |
| ------------- :|:-------------:|:-----|
|1|7|4|
|1|9|5|
|1|3|2|
|2|8|5|
|3|1|2|
|3|7|5|
|3|9|6|
|4|6|5|
|6|4|5|
|7|1|4|
|7|3|5|
|7|9|8|
|8|2|5|
|9|1|5|
|9|3|6|
|9|7|8|

本题有个坑点吧
就是输入的数 要在1~9 上 否则就应是 invalid

附本题代码

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
# include <string.h>
# include <stdio.h>
# include <iostream>
using namespace std;
int main()
{
   // freopen("in.txt", "r", stdin);
    //freopen("outt.txt", "w", stdout);
    int n,m,k;
    int a[12];
    int b[102];
    scanf("%d",&k);
    while(k--)
    {

        scanf("%d",&n);
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(int i=0; i<n; i++)
            scanf("%d",&a[i]);

        if(n<4)
        {
            printf("invalid\n");
            continue;
        }
        int f=1;
        for(int i=0; i<n-1; i++)
        {
            if(a[i]>9||a[i]<1)
                {
                f=0;
                break;
            }
            if(b[a[i]]==1)
            {
                f=0;
                break;
            }
            b[a[i]]=1;
            if(a[i]==1)
            {
                if((a[i+1]==3&&b[2]==0)||(a[i+1]==7&&b[4]==0)||(a[i+1]==9&&b[5]==0))
                    f=0;
            }
            if(a[i]==2)
            {
                if(a[i+1]==8&&b[5]==0)
                    f=0;
            }
            if(a[i]==3)
            {
                if((a[i+1]==1&&b[2]==0)||(a[i+1]==7&&b[5]==0)||(a[i+1]==9&&b[6]==0))
                    f=0;
            }
            if(a[i]==4)
            {
                if(a[i+1]==6&&b[5]==0)
                    f=0;
            }
            if(a[i]==6)
            {
                if(a[i+1]==4&&b[5]==0)
                    f=0;
            }
            if(a[i]==7)
            {
                if((a[i+1]==1&&b[4]==0)||(a[i+1]==3&&b[5]==0)||(a[i+1]==9&&b[8]==0))
                    f=0;
            }
            if(a[i]==8)
            {
                if(a[i+1]==2&&b[5]==0)
                    f=0;
            }
            if(a[i]==9)
            {
                if((a[i+1]==1&&b[5]==0)||(a[i+1]==3&&b[6]==0)||(a[i+1]==7&&b[8]==0))
                    f=0;
            }
             // cout<<a[i]<<" "<<b[i]<<endl;
        }
        if(b[a[n-1]]==1||a[n-1]>9||a[n-1]<1)
            f=0;
        if(f==0)
          printf("invalid\n");
        else
            printf("valid\n");
    }
    return 0;
}