ZOJ - 3861 Valid Pattern Lock（dfs或其他，兩種解法）

ZOJ - 3861 Valid Pattern Lock（dfs或其他，兩種解法）

Valid Pattern Lock Time Limit: 2000MS   Memory Limit: 65536KB   64bit IO Format: %lld & %llu

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:

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 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