UVA - 129 Krypton Factor 回溯+剪枝

题目大意：给出N种字母，要求用这N种字母组成一个困难的串，困难的串指在串中没有相连的两个子串相同，要求输出第M个困难的串

解题思路：像八皇后一样，前面判断的就不需要再去判断了，直接往后判断即可

#include<cstdio>
#include<cstring>

int n,L;
int ans[100];
bool flag;
int cnt;

bool judge(int cur) {

	for(int i = 1; i <= (cur+1) / 2 ; i++) {
		bool equal = 1;
		for(int j = 0;  j < i; j++)
			if(ans[cur-j] != ans[cur-i-j]) {
				equal = 0;
				break;
			}	
		if(equal)
			return false;	
	}
	return true;
}

void output(int cur) {
	for(int i = 0; i <= cur ; i++) {
		if(i % 4 == 0 && i > 0) {
			if(i % 64 == 0 && i > 0) 
				printf("\n");
			else
				printf(" ");	
		}
	printf("%c",'A' + ans[i]);
	}
	printf("\n%d\n",cur+1);
}

int dfs(int cur) {

	for(int i = 0; i < L; i++) {
		ans[cur] = i;
		if(judge(cur)) {
			cnt++;
			if(cnt == n ) {
				output(cur);
				return 1;
			}
			if(dfs(cur+1))
				return 1;
		}
	}
	return 0;
}

int main() {
	while(scanf("%d%d",&n,&L) != EOF && n + L) { 
		cnt = 0;
		dfs(0);	
	}
	return 0;
}