7-4练习了回溯法,这道7-5则是练习了回溯法+八皇后
题意并不是很容易理解,需要多读几遍原文,确保理解无误。
仔细读题后发现这道题是在深度优先枚举字母的排列,并加入了“困难”这一限制条件(类似于八皇后中的皇后不能相互攻击的意义)
先想出最简单的解法:
枚举字母串(书中所介绍的递归排列枚举算法),每次产生一个新串都进行检查。
检查是否“困难”的方法是:外层循环枚举子串长度;中层循环枚举左侧子串的起始位置;内层循环枚举子串中的字符的位置
直觉上来说,这个方法就太笨重了。实际上这个方法进行了很多重复的工作:
每次在原有字母串基础上增加一位字母新产生的字母串中,只有最后一位字母是新增的,如果将这一位字母去掉,则前面的字母串已经是“困难”的了。因此上面的方法中,中层循环可以去掉,然后将枚举方向改为从后向前。
这样就可以避免重复检查相同的字母串
一个细节需要注意:
因为本题不需要输出多个解,而是找到目标后即可输出,所以dfs时如果找到了解,应该立刻返回上层。
Run Time: 0.012s
// UVa #LT7-5.129.cpp #include<cstring> #include<cstdlib> #include<cstdio> #define maxn 500 using namespace std; //Global Variables. int n, L, cnt; int sequence[maxn]; ///// int is_hard(int cur) { int ok = 1; for(int k = 1; 2*k <= cur + 1; k ++) { int equal = 1; for(int j = 0; j < k; j ++) { if(sequence[cur - k - j] != sequence[cur - j]) { equal = 0; break; } } if(equal) { ok = 0; break; } } return ok; } int solve(int cur) { if(cnt++ == n) { for(int i = 0; i < cur; i ++) { if(!(i%4) && i && ((i)%64)) {printf(" ");} if(!((i)%64) && i) printf("\n"); printf("%c", sequence[i] + 'A'); } printf("\n%d\n", cur); return 1; } else { for(int i = 0; i < L; i ++) { sequence[cur] = i; if(is_hard(cur)) { if(solve(cur + 1)) return 1; } } } return 0; } int main() { while(scanf("%d%d", &n, &L) && n && L) { memset(sequence, -1, sizeof(sequence)); cnt = 0; solve(0); } return 0; }