UVa 129 Krypton Factor 어려운 문자열(dfs 반복 검색)

4108 단어 DFS

거슬러 올라가는 방법은 모든 하위 문자열이 아니라 현재 문자열의 접미사만 판단할 수 있다
#include<iostream>

#include<cstdio>

using namespace std;

int s[1000];

int n,l,cnt;

int bfs(int cur)

{

    if(cnt++==n)

    {

        for(int i=0; i<cur; i++)

            printf("%c",'A'+s[i]);

        cout<<endl;

        return 0;

    }

    for(int i=0; i<l; i++)

    {

        s[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(s[cur-k]!=s[cur-k-j])

                {

                    equal=0;

                    break;

                }

            if(equal)

            {

                ok=0;

                break;

            }

        }

        if(ok)  if(!bfs(cur+1))

                return 0;

    }

    return 1;

}



int main()

{

    while(cin>>n>>l&&n&&l)

    {

        cnt=0;

        bfs(0);

    }

    return 0;

}

좋은 웹페이지 즐겨찾기