2016年6月7日 星期二

UVA 146 ID Codes (遞迴解)

/*
    題目連結

    STL固然好用 但是學習怎麼自己寫也是重要的!
    特別是自己寫也不難的時候

    用遞迴來找 全部的permutation應該是不難的
    (沒寫過的人 其實可以想像一些本篇的code 裡DFS的flag
    永遠都是 false 的情況)

    在這裡當 flag==true時 我們直接"設定"我們變數c的值
    那就很像我們在找 全部的排列 但是我們直接跳到給定的排列
    然後 繼續找下一個排列 (也就是successor)
*/
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

char s[51]; int sn;
int cnt[26];
char now[51];

bool DFS(int O, bool flag)
{
    if( O == sn )
    {
        now[O] = '\0';
        return !flag;
    }

    char c = flag?s[O]:'a';

    for(; c <= 'z'; c++)
        if( cnt[c-'a'] )
        {
            cnt[c-'a']--;
            now[O] = c;

            if( DFS(O+1, flag&&c==s[O]) ) return true;
            cnt[c-'a']++;
        }

    return false;
}

int main()
{
    while(1)
    {
        scanf("%s", s), sn = strlen(s);
        if( !strcmp(s, "#") ) break;

        memset(cnt, 0, sizeof(cnt));

        for(int si = 0; si < sn; si++)
            cnt[s[si]-'a']++;

        if( DFS(0, true) ) printf("%s\n", now);
        else puts("No Successor");
    }
}

沒有留言:

張貼留言