程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ZOJ 3861 Valid Pattern Lock DFS

ZOJ 3861 Valid Pattern Lock DFS

編輯:C++入門知識

ZOJ 3861 Valid Pattern Lock DFS


 

 

Valid Pattern Lock

Time Limit: 2 Seconds Memory Limit: 65536 KB

 

Pattern lock security is generally used in Android handsets instead of a password. The pattern lock can be set by joining points on a 3 × 3 matrix in a chosen order. The points of the matrix are registered in a numbered order starting with 1 in the upper left corner and ending with 9 in the bottom right corner.

valid_pattern_lock

A valid pattern has the following properties:

  • A pattern can be represented using the sequence of points which it's touching for the first time (in the same order of drawing the pattern). And we call those points as active points.For every two consecutive points A and B in the pattern representation, if the line segment connecting A and B passes through some other points, these points must be in the sequence also and comes before A and B, otherwise the pattern will be invalid.In the pattern representation we don't mention the same point more than once, even if the pattern will touch this point again through another valid segment, and each segment in the pattern must be going from a point to another point which the pattern didn't touch before and it might go through some points which already appeared in the pattern.

     

    Now you are given n active points, you need to find the number of valid pattern locks formed from those active points.

    Input

    There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

    The first line contains an integer n (3 ≤ n ≤ 9), indicating the number of active points. The second line contains n distinct integers a1, a2, … an (1 ≤ ai ≤ 9) which denotes the identifier of the active points.

    Output

    For each test case, print a line containing an integer m, indicating the number of valid pattern lock.

    In the next m lines, each contains n integers, indicating an valid pattern lock sequence. The m sequences should be listed in lexicographical order.

    Sample Input

    1
    3
    1 2 3
    

    Sample Output

    4
    1 2 3
    2 1 3
    2 3 1
    3 2 1
    

    Author: LIN, Xi
    Source: The 15th Zhejiang University Programming Contest
    Submit Status

     

     

    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    
    using namespace std;
    
    set st;
    vector vi;
    
    bool vis[20];
    int n;
    bool go[30];
    bool graph[5][5];
    int XY[10][2]={{0,0},{1,1},{1,2},{1,3},{2,1},{2,2},{2,3},{3,1},{3,2},{3,3}};
    int TU[4][4]=
    {
        0,0,0,0,
        0,1,2,3,
        0,4,5,6,
        0,7,8,9
    };
    
    const int dir_x[16]={-1,-1,-1,0,0,1,1,1,-1,-1,1,1,-2,-2,2,2};
    const int dir_y[16]={-1,0,1,-1,1,-1,0,1,-2,2,-2,2,-1,1,-1,1};
    
    bool isIn(int a,int b)
    {
        if((a<=0||a>3)||(b<=0||b>3)) return false;
        return true;
    }
    
    int as[10];
    
    void output(int x)
    {
        int na=0;
        while(x)
        {
            as[na++]=x%10;
            x/=10;
        }
        for(int i=na-1;i>=0;i--)
            printf(%d%c,as[i],(i==0)?10:32);
    }
    
    void dfs(int x,int y,int u,int nb,int deep)
    {
        if(deep==n-1)
        {
            if(st.count(nb)==0)
            {
                st.insert(nb);
                vi.push_back(nb);
            }
            return ;
        }
        for(int i=0;i<16;i++)
        {
            for(int j=1;j<=2;j++)
            {
                if(j==1)
                {
                    int nx=x+dir_x[i],ny=y+dir_y[i];
                    if(isIn(nx,ny)==false) continue;
                    int v=TU[nx][ny];
                    if(go[v]==false) continue;
                    if(vis[v]==true) continue;
                    vis[v]=true;
                    dfs(nx,ny,v,nb*10+v,deep+1);
                    vis[v]=false;
                }
                else if(j==2)
                {
                    int nx=x+dir_x[i]*2,ny=y+dir_y[i]*2;
                    if(isIn(nx,ny)==false) continue;
                    /// check mid
                    int xx=x+dir_x[i],yy=y+dir_y[i];
                    int tv=TU[xx][yy],vv=TU[nx][ny];
                    if(vis[tv]==false) continue;
                    if(go[tv]==false) continue;
                    if(vis[vv]==true) continue;
                    if(go[vv]==false) continue;
                    vis[vv]=true;
                    dfs(nx,ny,vv,nb*10+vv,deep+1);
                    vis[vv]=false;
                }
            }
        }
    }
    
    int main()
    {
        int T_T;
        scanf(%d,&T_T);
        while(T_T--)
        {
            scanf(%d,&n);
            memset(graph,false,sizeof(graph));
            memset(go,false,sizeof(go));
            st.clear(); vi.clear();
            for(int i=0;i

     

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved