HDOJ 5641 King's Phone(シミュレーション)

10951 ワード

King's Phone
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 2156 Accepted Submission(s): 524
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 square lattice, the three points in the first line are labeled as
1,2,3 , the three points in the second line are labeled as
4,5,6 , and the three points in the last line are labeled as
7,8,9 .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 is valid, but
3724 is invalid).
His password has a length for a positive integer
k(1≤k≤9) , the password sequence is
s1,s2...sk(0≤si
Input
The first line contains a number
T(0For each test case, there are only one line. the first first number
k ,represent the length of the password, then
k numbers, separated by a space, representing the password sequence
s1,s2...sk .

Output
Output exactly
T lines. For each test case, print `valid` if the password is valid, otherwise print `invalid`

Sample Input

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.

タイトル:

    ，           ，        。                。        
 $\times 3$

構想:直接書けばいいので、彼をマトリクスとして、入力数が1-9の範囲内ではない可能性があることに注意してください.
acコード:

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stack>
#include<set>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#define MAXN 1010000
#define LL long long
#define ll __int64
#define INF 0xfffffff
#define mem(x) memset(x,0,sizeof(x))
#define PI acos(-1)
#define eps 1e-8
using namespace std;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
double dpow(double a,ll b){double ans=1.0;while(b){if(b%2)ans=ans*a;a=a*a;b/=2;}return ans;}
//head
int v[10][10];
int a[MAXN];
int main()
{
    int t,i;
    scanf("%d",&t);
    while(t--)
    {
        int k;
        scanf("%d",&k);
        for(i=0;i<k;i++)
        scanf("%d",&a[i]);
        if(k<4)
        {
            printf("invalid
");
            continue;
        }
        mem(v);
        int x=a[0]%3?a[0]/3+1:a[0]/3,y=a[0]%3?a[0]%3:3;
        //printf("x=%d y=%d
",x,y);
        v[x][y]=1;
        int bz=0;
        if(a[0]<1||a[0]>9)
        bz=1;
        for(i=1;i<k;i++)
        {
            if(a[i]<1||a[i]>9)
            {
                bz=1;
                break;
            }
            int xx=a[i]%3?a[i]/3+1:a[i]/3,yy=a[i]%3?a[i]%3:3;
            //printf("xx=%d yy=%d
",xx,yy);
            if(v[xx][yy])
            {
                bz=1;
                break;
            }
            else
            {
                if(abs(x-xx)==2)
                {
                    if(abs(y-yy)==0)
                    {
                        if(!v[(xx+x)/2][y])
                        {
                            bz=1;
                            break;
                        }
                    }
                    else if(abs(y-yy)==2)
                    {
                        if(!v[(xx+x)/2][(yy+y)/2])
                        {
                            bz=1;
                            break;
                        }
                    }
                }
                else if(abs(abs(y-yy)==2))
                {
                    if(abs(x-xx)==0)
                    {
                        if(!v[x][(y+yy)/2])
                        {
                            bz=1;
                            break;
                        }
                    }
                }
            }
            v[xx][yy]=1,x=xx,y=yy;
        }
        printf(bz?"invalid
":"valid
");
    }
    return 0;
}

Amazon AWS Cloud9 開発環境を速攻で作る方法(令和最新版)

Java 7のSwitch文はStringをサポートする