HNUSTOJ-1675 Morse Code(DFS+字典序搜索)

1675: Morse Code

时间限制: 2 Sec  内存限制: 128 MB
提交: 73  解决: 33
[提交][状态][讨论版]

题目描述

摩尔斯电码（英语：Morse Code）是一种时通时断的信号代码，通过不同的排列顺序来表达不同的英文字母、数字和标点符号。是由美国人萨缪尔·摩尔斯在1836年发明。

                                                                                                    --摘自维基百科

摩尔斯电码的代码有点（.）,划（-）以及停顿组成。

常见的字符编码见下表：

 

现在我们有码文，可惜的是字符中间的停顿不见了，例如"-.-.", 可以被译码为"C", "KE","NN", "NTE", "TAE", "TEN", "TETE", 或 "TR". 

输入

仅有一行，由点和划构成的字符串，字符串长度不超过25。

输出

按字母序输出字符串所有可能的译码，每种情况占一行。

样例输入

--.-.

样例输出

GN

GTE

MAE

MEN

METE

MR

QE

TC

TKE

TNN

TNTE

TTAE

TTEN

TTETE

TTR

#include<iostream>

#include<cstring>

#include<cstdio>

#include<string>

#include<map>

#include<set>

using namespace std;

char dic[][]={

 ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---",

 "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-",

 "..-", "...-", ".--", "-..-", "-.--", "--.."

};

int len;

char a[], b[];

bool Strcmp(int cur, char *str){

    int len = strlen(dic[cur]);

    for(int i = ; i < len; i++)

        if(*(str + i) != dic[cur][i]) return false;

    return true;

}

void DFS(int cur, int l){

    if(cur == len) {

        for(int i = ; i < l; i++) printf("%c", a[i]);

        printf("\n"); return;

    }

    for(int i = ; i < ; i++){

        if(Strcmp(i, b + cur)){

            a[l] = 'A' + i;

            DFS(cur + strlen(dic[i]), l + );

        }

    }

}

int main(){

    scanf("%s", b);

    len = strlen(b);

    DFS( , );

}