hdu 5641 BestCoder Round #75

King's Phone

Accepts: 310

Submissions: 2980

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

问题描述

阅兵式上，国王见到了很多新奇东西，包括一台安卓手机。他很快对手机的图形解锁产生了兴趣。

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

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

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

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

他想设置的密码的长度为正整数  $k (1 \leq k \leq 9)$ ，密码序列为  $s_1 s_2...s_k(0le s_i < INT\_MAX)$ ，他想知道这个密码序列是否合法，这个问题交给了你。

输入描述

第一行一个整数表示测试组数： $T (0 < T \leq 100000)$  。

每组数据占一行，每行第一个数  $k$ ，设置密码的长度；接着  $k$  个正整数，之间用空格隔开，表示密码序列  $s_1s_2...s_k$ 。

输出描述

共  $T$  行。对每组数据，若合法输出 `valid`，否则输出 `invalid`。

输入样例

输出样例

invalid
valid
valid

Hint

对于第一组数据， $1$  到  $3$  跳过了路径上的点  $2$ ，所以不合法。

对于第二组数据， $1$  到  $3$  时点  $2$  已经被经过了，所以合法。

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

/*
hdu 5641 BestCoder Round #75

给你3*3的
1 2 3
4 5 6
7 8 9
就像手机滑动解锁，给你s1s2s3....sn问给的密码是否合适
1.至少有4位         2.中途不能有没走过的   3.走过之后不能走第二次
4.由于0≤s[i]<INT_MAX,所以要判断s[i]是否在1~9

像1->3就要先判断中间的2走过没，1->5 or 1->则都是合法的
所以每次对两个数进行一次判断即可

*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <map>
using namespace std;
typedef long long ll;
typedef long double ld;
#define lson (i<<1)
#define rson ((i<<1)|1)
const int maxn = 20;
int vis[maxn];
int a[maxn];

bool judge(int a,int b)
{
    if(a > b) swap(a,b);
    if(a == 1 && b == 9)
        return vis[5];
    else if(a == 1 && b == 3)
        return vis[2];
    else if(a == 1 && b == 7)
        return vis[4];
    else if(a == 3 && b == 9)
        return vis[6];
    else if(a == 2 && b == 8)
        return vis[5];
    else if(a == 3 && b == 7)
        return vis[5];
    else if(a == 4 && b == 6)
        return vis[5];
    else if(a == 7 && b == 9)
        return vis[8];
    else
        return 1;
}

int main()
{
    int T,m,n;
    scanf("%d",&T);
    while(T--)
    {
        int flag = 0;
        scanf("%d",&n);
        memset(vis,0,sizeof(vis));
        for(int i = 1; i <= n; i++)
        {
            scanf("%d",&a[i]);
            if(a[i] > 9 || a[i] < 1)
                flag = 1;
        }

        if(flag || n < 4)
        {
            printf("invalid
");
            continue;
        }
        vis[a[1]] = 1;
        for(int i = 2;i <= n;i++)
        {
            if(!judge(a[i],a[i-1]) || vis[a[i]])
                flag =1;
            vis[a[i]] = 1;
        }
        if(flag)
            printf("invalid
");
        else
            printf("valid
");
    }
    return 0;
}