题目:https://vjudge.net/problem/UVA-129

解题思路:


回溯法(for循环实现)

参考n皇后问题的解题思路:如欲把皇后放在(cur,i)单元格,则要判断当前(cur,i)位置的皇后是否和之前已经放置好的皇后产生冲突,而不是判断以前的皇后之间是否产生冲突。因为这种方法保证了之前放置的皇后之间一定不存在冲突。

同样的道理:对于题目中output给出的字符串们:

AB是在A的基础上产生的,AA不可以,AB可以

ABA是在AB的基础上产生的

ABAC是在ABA的基础上产生的,ABAA不可以(从后缀开始向前判断),ABAB不可以,ABAC可以

依次类推

所以只需要判断当前串的后缀,而非所有子串!

注意:

解只输出一次即可,所以要控制递归结束的条件!!!

不要有多余的空格,样例中第二个输出的字符串的末尾不应该有空格,否则会PE

最后一个输出的数字后面有换行不会报PE

ac代码:


#include <iostream>
#include <cmath>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <sstream>
#define maxn 100
using namespace std;
typedef long long ll;
int n,L,numb;
char ans[maxn];
char a[27]="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
bool is_hard(char ans[],int cur)
{
    bool hard;
    int num=1;
    while(num*2<=(cur+1))
    {
        hard=false;
        for(int i=0;i<num;i++)
        {
            if(ans[cur-i]!=ans[cur-num-i])//ABACAB 6-2-2 6-2
            {

                hard=true;//困难字符串
                break;
            }
        }
        if(!hard) return false;//只要在比较的过程中有一次比较失败即return
        num++;
    }
    return true;

}
int  answer(int cur)//cur个
{
    if(numb==n)
    {
        int i;
        for( i=0;i<cur;i++)
        {
            printf("%c",ans[i]);
            if(i%4==3)
            {
                if((i/4)==15)//16*4=64,最多只有一行多,(16*4-1)/4=15
                     printf("\n");
                else if(i!=(cur-1))
                    printf(" ");
            }
        }
        if(i!=63)
            printf("\n");
        printf("%d\n",cur);
        return 0;
    }
    else {
        for (int i = 0; i < L; i++)
        {
            ans[cur]=a[i];
            if(is_hard(ans,cur))
            {
                numb++;
                if(!answer(cur + 1)) return 0;
            }
        }
    }
    return  1;
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    while(scanf("%d %d",&n,&L))
    {
        if(n==0&&L==0) break;
        numb=0;
        ans[0]='\0';
        answer(0);
    }
    return 0;
}