UVa 10562 - Undraw the Trees (不限制儿子个数的树)

10562-Undraw the Trees

2073

29.14%

552

85.69%

题目链接：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=104&page=show_problem&problem=1503

题目类型： 数据结构， 二叉树

输入与输出：

Sample Professor’s TreesCorresponding Our Trees

2 A | -------- BCD || ----- - EF G # e | ---- f g #

(A(B()C(E()F())D(G()))) (e(f()g()))

题目大意：

左边的输入表示的是一棵树， 这棵树的一个结点可以有很多个儿子。所有的输入， 只要是可打印的字符，并且不是空格， ‘#’，’|‘， ’-‘的都是代表一个节点。

如果一个结点下方有‘|’则代表他有儿子。他的儿子们在一段连续‘-’的下面的结点。

分析与总结：

如果用建树的方法，初看可能比较复杂， 但是其实是很并不难的。我的方法是构造一个有MAXN个儿子指针的结点， 然后开一个和最大的输入尺寸一样的二维数组存结点，分别相对应

于输入的二维字符串数组。

然后对输出进行枚举，当碰到一个是结点的字符时，就对结点数组相对应结点找儿子， 找儿子用一个函数实现， 向下搜索出它的所有儿子即可。

最后构造完之后， 对这棵树进行前序遍历输出， 注意输出左右括号的位置。

按理说这题只要并不难的，但是却被恶心到了， 昨天晚上开始做的，想好思路后很快就敲好代码，过了样例之后自信满满的提交了，然后，看到了血红血红的Wrong answer，给了我当头一棒。之后就不断的调试，不断的WA。

然后就在网上找测试样例，结果发现也全部都可以过。这就说明一定不是我思路的问题， 肯定是一些细节或者边界条件没考虑到。

百度，谷歌被我翻了几十页，结果发现网上的解题报告全部都是用递归搜索解的，而且完全没有和我解题思路一样的。 更奇葩的是，我的队友也想了一个很奇葩的方法， 结果我们两个都卡了很久。

不断的WA，血淋淋的事实， 说明即使你认为自己是对的，确保是万无一失的， 也可能会有一些恶心的边界或者自己的思维漏洞而wa。

#include<cstdio>
#include<cctype>
#include<iostream>
#include<cstring>
#define MAXN 205
using namespace std;

class Node{
public:
    char data;
    Node *son[MAXN];
};

Node *root;
Node node[210][210];
char str[210][210];
int row;

inline bool isNode(char ch){
    if(isprint(ch) && ch!='-' && ch!='|' &&
            ch!=' ' && ch!='#')
        return true;
    return false;
}

void linkSon(int r, int c){
    if(r+3 >= row || str[r+1][c]!='|') return;
    int i,j;
    // 移动到有 ‘-’ 的最左边
    for(i=c; str[r+2][i]=='-'&&i>=0; --i) ;;
    int sonNum=0;
    i++;
    // 从最左边的‘-’往右枚举到最右边的'-'. 
    //这里特别要注意边界条件，就因为这个i<strlen(str[r+2])&&i<strlen(str[r+3])
    // 导致我郁闷了一个晚上+一个早上
    for( ; str[r+2][i]=='-'&&i<strlen(str[r+2])&&i<strlen(str[r+3]); ++i){
        if(isNode(str[r+3][i])){ // 如果是结点，链接起来
            node[r][c].son[sonNum++] = &node[r+3][i];
        }
    }
}

void dfs(Node *root){
    if(root){
        printf("%c", root->data);
        bool flag = true;
        for(int j=0; j<MAXN; ++j){
            if(root->son[j]!=NULL){
                flag = false;
                if(j==0) printf("(");
                dfs(root->son[j]);
            }
        }
        if(flag) printf("()");
        else printf(")");
    }
}  
void Solve(){
    // 初始化
    for(int i=0; i<row; ++i){
        for(int j=0; j<strlen(str[i]); ++j){
            for(int k=0; k<MAXN; ++k)
                node[i][j].son[k] = NULL; 
        }
    }   
    root = NULL;
    for(int i=0; i< row; ++i){
        for(int j=0; j<strlen(str[i]); ++j){
            if(isNode(str[i][j])){
                if(root==NULL){
                    node[i][j].data = str[i][j];
                    root = &node[i][j];
                    linkSon(i,j);
                    break;
                }
                else{
                    node[i][j].data = str[i][j];
                    linkSon(i, j);
                }
            }
        }
    }   
    printf("(");
    dfs(root);
    printf(")\n");
}

int main(){
 //   freopen("input.txt", "r", stdin);
    int T;
    scanf("%d%*c", &T);
    while(T--){
        row=3;
        memset(str[2], 0, sizeof(str[2]));
        while(gets(str[row])){
            if(str[row][0]=='#') break;
            ++row;
            memset(str[row], 0, sizeof(str[row]));// 初始化，避免遗留上次的数据下来
        }
        Solve();
    }
    return 0;
}      

—— 生命的意义，在于赋予它意义。

原创http://blog.csdn.net/shuangde800，By D_Double