首页 > 代码库 > POJ - 1780 Code （欧拉回路+手写DFS）

POJ - 1780 Code （欧拉回路+手写DFS）

2024-07-16 14:01:55   221人阅读

Description

KEY Inc., the leading company in security hardware, has developed a new kind of safe. To unlock it, you don‘t need a key but you are required to enter the correct n-digit code on a keypad (as if this were something new!). There are several models available, from toy safes for children (with a 2-digit code) to the military version (with a 6-digit code).

The safe will open as soon as the last digit of the correct code is entered. There is no "enter" key. When you enter more than n digits, only the last n digits are significant. For example (in the 4-digit version), if the correct code is 4567, and you plan to enter the digit sequence 1234567890, the door will open as soon as you press the 7 key.

The software to create this effect is rather simple. In the n-digit version the safe is always in one of 10n-1 internal states. The current state of the safe simply represents the last n-1 digits that have been entered. One of these states (in the example above, state 456) is marked as the unlocked state. If the safe is in the unlocked state and then the right key (in the example above, 7) is pressed, the door opens. Otherwise the safe shifts to the corresponding new state. For example, if the safe is in state 456 and then you press 8, the safe goes into state 568.

A trivial strategy to open the safe is to enter all possible codes one after the other. In the worst case, however, this will require n * 10n keystrokes. By choosing a good digit sequence it is possible to open the safe in at most 10n + n - 1 keystrokes. All you have to do is to find a digit sequence that contains all n-digit sequences exactly once. KEY Inc. claims that for the military version (n=6) the fastest computers available today would need billions of years to find such a sequence - but apparently they don‘t know what some programmers are capable of...

Input

The input contains several test cases. Every test case is specified by an integer n. You may assume that 1<=n<=6. The last test case is followed by a zero.

Output

For each test case specified by n output a line containing a sequence of 10n + n - 1 digits that contains each n-digit sequence exactly once.

Sample Input

1
2
0

Sample Output

0123456789
00102030405060708091121314151617181922324252627282933435363738394454647484955657585966768697787988990

题意：破解一套1-6位长度密码的系统，寻找这样一个序列：对于N位的密码10^N+N-1长度的连续的长为N的串能够枚举完所有的密码。

思路：做的头疼，懒得写了。就拿别人的题解吧：对于每一个长度为n的串，让该串的前n-1位为一个节点，后n-1位为另一个节点这样就确定了这个串。

n 位数有10n 种编码方案（即10n 组数），要使得一个数字序列包含这10n 组n 位数，且序列的长


度最短，唯一的可能是每组数出现一次且仅一次、且前一组数的后n-1 位是后一组数的前n-1 位，


这样10n 组数各取1 位，共10n 位，再加上最后一组数的后n-1 位，总位数是10n + n - 1。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn = 1000015;

struct Edge {
	int v, next;
} e[maxn];
int n, mod, head[maxn], stk[maxn];
int idx, lim, edge, top;
char vis[maxn];
 
void insert(int a, int b) {
	e[idx].v = b;
	e[idx].next = head[a];
	head[a] = idx++;
}

void dfs() {
	stk[top++] = 0;
	while (1) {
		int flag = 0;
		int v = stk[top-1];
		if (top >= idx-(n-2))
			return;
		for (int i = head[v]; i != -1; i = e[i].next)
			if (!vis[i]) {
				flag = 1;
				vis[i] = 1;
				stk[top++] = e[i].v;
				break;
			}
		if (!flag)
			--top;
	}
}

int main() {
	while (scanf("%d", &n) != EOF && n) {
		if (n == 1) {
			printf("0123456789\n");
			continue;
		}
		idx = top = 0;
		memset(head, -1, sizeof(head));
		memset(vis, 0, sizeof(vis));
		lim = 1;
		for (int i = 1; i < n; i++)
			lim *= 10;
		edge = lim * 10;
		mod = lim / 10;
		for (int i = 0; i < lim; i++)
			for (int j = 9; j >= 0; j--)
				insert(i, (i%mod)*10+j);
		dfs();
		for (int i = 0; i < top-1; i++)
			printf("%d", stk[i]/mod);
		printf("%d", stk[top-1]);
		for (int i = 1; i < n; i++)
			printf("0");
		printf("\n");
	}
	return 0;
}


联系
我们