Submit Status

Description

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.

A valid pattern has the following properties:

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 a₁, a₂, …a_n (1 ≤ a_i ≤ 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

规则就是手机手势解锁的规则，用一个数组把处于两个数字中间的数字存下来，方便判断，这题有两种思路，一种是dfs，一种是枚举所有n个数的排列，判断是否符合。dfs是要记录路径的，而且路径是多条有公用的小段，这就有点难了，还好我机智的用来个int把答案存起来，可是处理起来操作较多，用时竟然比再用一个dfs还多。第二种方法很直观。

贴下两代码：

dfs

?

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         using namespace std; int mp[12][12]; int n, kind, used[123], a[123], b[123]; int result[400000]; int ans; void init() { mp[1][3] = 2; mp[3][1] = 2; mp[1][7] = 4; mp[7][1] = 4; mp[1][9] = 5; mp[9][1] = 5; mp[2][8] = 5; mp[8][2] = 5; mp[3][7] = 5; mp[7][3] = 5; mp[3][9] = 6; mp[9][3] = 6; mp[4][6] = 5; mp[6][4] = 5; mp[7][9] = 8; mp[9][7] = 8; } void dfs(int cur, int x) { ans = ans * 10 + cur; if (x == n) { kind++; result[kind] = ans; return; } for (int i = 0; i
        
         > t; init(); while (t--) { scanf("%d", &n); for (int i = 0; i
         
           另一种
          
?
          
#include
           
            
#include
            
              #include
             
               #include
              
                #include
               
                 using namespace std; int a[11]; int mp[11][11]; int vis[11]; int n, kind; int result[400000][10]; void init() { mp[1][3] = 2; mp[3][1] = 2; mp[1][7] = 4; mp[7][1] = 4; mp[1][9] = 5; mp[9][1] = 5; mp[2][8] = 5; mp[8][2] = 5; mp[3][7] = 5; mp[7][3] = 5; mp[3][9] = 6; mp[9][3] = 6; mp[4][6] = 5; mp[6][4] = 5; mp[7][9] = 8; mp[9][7] = 8; } bool can() { int v; vis[a[0]] = 1; for (int i = 1; i < n; i++) { v = mp[a[i]][a[i - 1]]; if (!(!vis[a[i]] && (!v || vis[v]))) return false; vis[a[i]] = 1; } return true; } int main() { int t; cin >> t; init(); while (t--) { scanf("%d", &n); for (int i = 0; i