HDOJ 5641-King's Phone【模拟】

川长思鸟来 2022-08-21 03:15 2阅读 0赞

# King's Phone #

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 257 Accepted Submission(s): 86

Problem Description

In a military parade, the King sees lots of new things, including an Andriod Phone. He becomes interested in the pattern lock screen.  
  
The pattern interface is a  3×3![Image 1][] square lattice, the three points in the first line are labeled as  1,2,3![Image 1][], the three points in the second line are labeled as  4,5,6![Image 1][], and the three points in the last line are labeled as  7,8,9![Image 1][]。The password itself is a sequence, representing the points in chronological sequence, but you should follow the following rules:  
  
\- The password contains at least four points.  
  
  
\- Once a point has been passed through. It can't be passed through again.  
  
\- The middle point on the path can't be skipped, unless it has been passed through(  3427![Image 1][] is valid, but  3724![Image 1][] is invalid).  
  
His password has a length for a positive integer  k(1≤k≤9)![Image 1][], the password sequence is  s![Image 1][]1![Image 1][],s![Image 1][]2![Image 1][]...s![Image 1][]k![Image 1][](0≤s![Image 1][]i![Image 1][]<INT\_MAX)![Image 1][] , he wants to know whether the password is valid. Then the King throws the problem to you.

Input

The first line contains a number&nbsp;  T(0<T≤100000)![Image 1][], the number of the testcases.  
  
For each test case, there are only one line. the first first number&nbsp;  k![Image 1][]，represent the length of the password, then  k![Image 1][] numbers, separated by a space, representing the password sequence  s![Image 1][]1![Image 1][],s![Image 1][]2![Image 1][]...s![Image 1][]k![Image 1][]![Image 1][].

Output

Output exactly  T![Image 1][] lines. For each test case, print \`valid\` if the password is valid, otherwise print \`invalid\`

Sample Input

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

Sample Output

invalid
    valid
    valid
    
    hint:
    For test case #1：The path $1\rightarrow 3$ skipped the middle point $2$, so it's invalid.
    
    For test case #2：The path $1\rightarrow 3$ doesn't skipped the middle point $2$, because the point 2 has been through, so it's valid.
    
    For test case #2：The path $8\rightarrow 1 \rightarrow 6 \rightarrow 7$ doesn't have any the middle point $2$, so it's valid.

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    struct node
    {
        int wc[100],ll;
    }num[100];
    int map[10000];
    bool vis[10000];
    int main()
    {
        int i,j;
        for(i=1;i<=9;i++)
        {
            num[i].ll=0;
            int ll1=0;
            for(j=1;j<=9;j++)
            {
                if(i==1)
                {
                    if(j==2||j==4||j==5||j==6||j==8)
                    {
                        num[i].wc[ll1++]=j;
                        num[i].ll++;
                    }
                }
                if(i==2)
                {
                    if(j==1||j==3||j==4||j==5||j==6||j==7||j==9)
                    {
                        num[i].wc[ll1++]=j;
                        num[i].ll++;
                    }
                }
                if(i==3)
                {
                    if(j==2||j==4||j==5||j==8||j==6)
                    {
                        num[i].wc[ll1++]=j;
                        num[i].ll++;
                    }
                }
                if(i==4)
                {
                    if(j==1||j==2||j==3||j==5||j==8||j==7||j==9)
                    {
                        num[i].wc[ll1++]=j;
                        num[i].ll++;
                    }
                }
                if(i==5)
                {
                    if(j==1||j==2||j==3||j==4||j==6||j==8||j==7||j==9)
                    {
                        num[i].wc[ll1++]=j;
                        num[i].ll++;
                    }
                }
                if(i==6)
                {
                    if(j==1||j==2||j==3||j==5||j==8||j==7||j==9)
                    {
                        num[i].wc[ll1++]=j;
                        num[i].ll++;
                    }
                }
                if(i==7)
                {
                    if(j==2||j==4||j==5||j==8||j==6)
                    {
                        num[i].wc[ll1++]=j;
                        num[i].ll++;
                    }
                }
                if(i==8)
                {
                    if(j==1||j==3||j==4||j==5||j==6||j==7||j==9)
                    {
                        num[i].wc[ll1++]=j;
                        num[i].ll++;
                    }
                }
                if(i==9)
                {
                    if(j==4||j==2||j==5||j==8||j==6)
                    {
                        num[i].wc[ll1++]=j;
                        num[i].ll++;
                    }
                }
            }
        }
        int T;
        scanf("%d",&T);
        while(T--)
        {
            int n;
            scanf("%d",&n);
            int i,j;
            int hh=0;
            for(i=0;i<n;i++)
            {
                scanf("%d",&map[i]);
                if(map[i]>9||map[i]<1)
                {
                	hh=1;
                }
            }
            if(n<4)
            {
            	printf("invalid\n");
            	continue;
            }
            if(hh==1)
            {
                printf("invalid\n");
            }
            else
            {
                memset(vis,false,sizeof(vis));
                bool ans=false;
                for(i=0;i<n-1;i++)
                {
                    vis[map[i]]=true;
                    bool ee=false;
                    for(j=0;j<num[map[i]].ll;j++)
                    {
                        if(map[i+1]==num[map[i]].wc[j]&&vis[map[i+1]]==false)
                        {
                            ee=true;
                            break;
                        }
                    }
                    if(ee==true)
                    {
                        continue;
                    }
                     else if(ee==false&&vis[map[i+1]]==false)
                    {
                        if(map[i]==1)
                        {
                            if(map[i+1]==7&&vis[4]==true)
                            {
                                continue;
                            }
                            if(map[i+1]==3&&vis[2]==true)
                            {
                                continue;
                            }
                            if(map[i+1]==9&&vis[5]==true)
                            {
                                continue;
                            }
                        }
                        if(map[i]==2)
                        {
                            if(map[i+1]==8&&vis[5]==true)
                            {
                                continue;
                            }
                        }
                        if(map[i]==3)
                        {
                            if(map[i+1]==1&&vis[2]==true)
                            {
                                continue;
                            }
                            if(map[i+1]==7&&vis[5]==true)
                            {
                                continue;
                            }
                            if(map[i+1]==9&&vis[6]==true)
                            {
                                continue;
                            }
                        }
                        if(map[i]==4)
                        {
                            if(map[i+1]==6&&vis[5]==true)
                            {
                                continue;
                            }
                        }
                        if(map[i]==6)
                        {
                            if(map[i+1]==4&&vis[5]==true)
                            {
                                continue;
                            }
                        }
                        if(map[i]==7)
                        {
                            if(map[i+1]==1&&vis[4]==true)
                            {
                                continue;
                            }
                            if(map[i+1]==3&&vis[5]==true)
                            {
                                continue;
                            }
                            if(map[i+1]==9&&vis[8]==true)
                            {
                                continue;
                            }
                        }
                        if(map[i]==8)
                        {
                            if(map[i+1]==2&&vis[5]==true)
                            {
                                continue;
                            }
                        }
                        if(map[i]==9)
                        {
                            if(map[i+1]==1&&vis[5]==true)
                            {
                                continue;
                            }
                            if(map[i+1]==7&&vis[8]==true)
                            {
                                continue;
                            }
                            if(map[i+1]==3&&vis[6]==true)
                            {
                                continue;
                            }
                        }
                        break;
                    }
                    else
                    break;
                }
                if(i!=(n-1))
                {
                    printf("invalid\n");
                }
                else
                {
                    printf("valid\n");
                }
            }
            
        }
        return 0;
    }

[Image 1]: