题目链接： https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=3&problem=65&mosmsg=Submission+received+with+ID+18947559 代码：
#include<cstdio> #include<cstring> #include<iostream> using namespace std; const int MAXN = 100; char a[MAXN]; int n, L, cnt; bool dfs(int cur) { /*每递归调用一次，形成的搜索串的名次就会加一，用cnt记录。其中后缀++表示的是先判断，后相加*/ /*cur表示递归的深度，即符合题目要求的串的长度*/ if (cnt++ == n) { for (int i = 0; i < cur; i++) { printf("%c", 'A' + a[i]); if ((i + 1) % 4 == 0) { if ((i + 1) % 64 == 0) cout << endl; else if (i != cur - 1)putchar(' '); } } if (cur % 64) cout << endl; printf("%d\n", cur); return false; } for (int i = 0; i < L; i++) { ///每一个a[cur]一共有L种选择 a[cur] = i; int ok = 1; for (int j = 1; j * 2 <= cur + 1; j++) { int equal = 1; ///判断是否有连续相同的字符串 for (int k = 0; k < j; k++) { if (a[cur - k] != a[cur - k - j]) { equal = 0; break; } } if (equal) { ok = 0; break; } } if (ok) ///递归搜索。如果找到解，则直接退出。 if (!dfs(cur + 1)) return false; } return true; } int main() { while (scanf("%d%d", &n, &L)==2) { if (n == 0 && L == 0) break; memset(a, 0, sizeof(a)); cnt = 0; dfs(0); } return 0; }注意： 1、根据题意描述，易知在枚举第cur位时，只用检查它添加后该串是否合法，而不必去检查cur之前的串是否合法，因为这一步检查在枚举cur之前早已经做过了。这一点类似于八皇后问题（只需要判断当前皇后是否和前面的皇后冲突，并不需要判断以前的皇后是否相互冲突-那些皇后在以前已经判断过了）。 2、注意此题的输出，《算法竞赛入门经典》并没有描述正确的输入 3、 这一步作用很大，减掉很多不必要的尝试。
另外举出一个会耗很多多余的时间的代码（Running Error）
#include<cstdio> #include<cstring> #include<iostream> using namespace std; const int MAXN = 100; char a[MAXN]; int n, L, cnt; void dfs(int cur) { ///每递归调用一次，形成的搜索串的名次就会加一，用cnt记录。其中后缀++表示的是先判断，后相加 ///cur表示递归的深度，即符合题目要求的串的长度 if (cnt++ == n) { for (int i = 0; i < cur; i++) { printf("%c", 'A' + a[i]); if ((i + 1) % 4 == 0) { if ((i + 1) % 64 == 0) cout << endl; else if (i != cur - 1)putchar(' '); } } if (cur % 64) cout << endl; printf("%d\n", cur); return ; } for (int i = 0; i < L; i++) { ///每一个a[cur]一共有L种选择 a[cur] = i; int ok = 1; for (int j = 1; j * 2 <= cur + 1; j++) { int equal = 1; for (int k = 0; k < j; k++) ///判断是否有连续相同的字符串 { if (a[cur - k] != a[cur - k - j]) { equal = 0; break; } } if (equal) { ok = 0; break; } } if (ok) //if (!dfs(cur + 1)) // return false; dfs(cur+1); } // return true; } int main() { while (scanf("%d%d", &n, &L)==2) { if (n == 0 && L == 0) break; memset(a, 0, sizeof(a)); cnt = 0; dfs(0); } return 0; }这个代码在提交时会报Running Error。栈溢出。 在debug中看的很清楚。值得深思！！！
