ZOJ 3861 - Valid Pattern Lock
Time Limit:2000MS Memory Limit:65536KB 64bit IO Format:%lld & %llu
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:
- 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
#include <iostream> #include <cmath> #include <stdio.h> #include <string> #include <cstring> #include <map> #include <set> #include <vector> #include <stack> #include <queue> #include <iomanip> #include <algorithm> #include <memory.h> using namespace std; int n; int a[10]; int may[10]; bool vis[10]; int mp[10][10]; int num; void init() { memset(mp,0,sizeof(mp)); mp[1][9]=mp[9][1]=mp[3][7]=mp[7][3]=mp[2][8]=mp[8][2]=mp[4][6]=mp[6][4]=5; mp[1][3]=mp[3][1]=2; mp[1][7]=mp[7][1]=4; mp[7][9]=mp[9][7]=8; mp[3][9]=mp[9][3]=6; } int ans[400000][10]; void show() { for(int i=0; i<n; i++) cout<<may[i]<<' '; cout<<endl; } bool judge() { int viss[10]; memset(viss,0,sizeof(viss)); viss[0]=-1; int s1=may[0],s2; viss[s1]=1; for(int i=1; i<n; i++) { s2=may[i]; if(viss[s2]==1) return false; if(mp[s1][s2]!=0&&viss[mp[s1][s2]]==0) return false; s1=s2; viss[s2]=1; } for(int i=0; i<n; i++) { ans[num][i]=may[i]; } num++; return true; } void dfs(int p) { if(p==n) { judge(); return; } for(int i=0; i<n; i++) { if(vis[a[i]]==0) { may[p]=a[i]; vis[a[i]]=1; dfs(p+1); vis[a[i]]=0; } } } int main() { init(); int T; cin>>T; while(T--) { num=0; cin>>n; for(int i=0; i<n; i++) scanf("%d",&a[i]); sort(a,a+n); dfs(0); cout<<num<<endl; for(int i=0; i<num; i++) { for(int j=0; j<n-1; j++) printf("%d ",ans[i][j]); printf("%d\n",ans[i][n-1]); } } return 0; }
最新文章
- 课堂Java小程序(加减乘除与验证码)
- Jenkins + svn + maven 构建持续集成环境搭建
- A20的板子笔记
- java 复习003
- EasyUI + Spring MVC + hibernate实现增删改查导入导出
- NDK如何调试系统核心动态库(无系统源码的情况)
- SMART原则_百度百科
- python+ueditor+七牛云存储整合
- 仿中关村win8频道(win8.zol.com.cn)下的tab效果
- “天龙八步”细说浏览器输入URL后发生了什么
- 操作dom获取datatable中的某一行的某一列的数据
- MySQL 命令总结
- AJAX缓存清理
- 设计模式-结构型模式,python组合模式
- es6学习笔记10--箭头函数
- F - A计划
- nginx map使用方法
- ScoketTimeout Exception浅析
- JS获取url传参
- 234. Palindrome Linked List(判断链表是否回文)