转载请注明：

仰望高端玩家的小清新 http://www.cnblogs.com/luruiyuan/

题目大意：

给定字符拼成的树，将这些树转换成特定的括号表示的树

思路：

首先，观察样例，可以发现就是先序遍历的顺序，因此可以确定dfs

但是，还有几个地方需要考虑：

同一级的结点，在同一级的括号中
由于顺序满足先序遍历，因此不需要存储树的括号表示法，更不需要构建树，直接在遍历过程中输出即可。
空树：即输入为：# 时的树的处理，我不建议在此进行特判，因为本题的条件非常简单，完全可以把这个情况纳入普通情况进行处理，详见代码 27行和 32行。
关于数组初始化的问题：这里数组必须初始化，我一开始为了效率不想初始化，但是马上就wa了，其原因在于（我个人推测），存在相对刁钻的数据，使得上一次的输入的tree中 ‘|’ 符号出现在了本次 tree 中某一行的 '\0' 之后，这样的话，在本次 tree 做 dfs 时，由于找到了上一次 tree 的 '|' 而导致读取到了上一次 tree 的数据。
森林，有可能某种情况下，可以给出多个根的树，这样就成为了一个森林，需要考虑多根情况。
"----"中我们其实不需要显式找出其右边界，只要知道左边界即可。
输出数据格式的问题：这里必须吐槽UVA的测试数据，原本我的输出是最后一行不再输出换行符，没想到UVA给我判了wa，把对最后一行的特判去掉后，最后一行也输出换行，才最终ac，出题人有点不注意细节啊，必须批评一波。
其他 trick：比如用 valid_node 函数中，用字符串匹配代替 if else；读取 tree 时通过 while 循环一行完成读取，而不必写成函数徒增复杂度；使用 fgets 和 sscanf 来读取含有多余空白符的数字。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 const int SIZE =  + ;

 char tree[SIZE][SIZE];

 int num = ; // tree num

 int cur = ; // cur num of row in tree

 bool valid_node(char ch);

 void dfs_tree(int row, int col);

 int main(){

     // use fgets() and sscanf() to read white char and then remove them.

     fgets(tree[], SIZE, stdin);

     sscanf(tree[], "%d", &num);

     while(num--){

         // read tree

         cur = ;

         // memset is compulsory because the '|' behind the '\0' of the last tree will

         // have a bad influence on current tree

         memset(tree, , sizeof(tree));

         // use fgets() instead of gets() to read tree in order to avoid overflow

         while(fgets(tree[cur], SIZE, stdin) != NULL && tree[cur][] != '#')cur++;

         // dfs - for the condition of forest

         printf("(");

         for(int i=; tree[][i]; i++)

             if(valid_node(tree[][i]))

                 dfs_tree(, i);

         // postprocess. If we use "if(num > 0)puts("");", it will cause "wrong answer"

         printf(")\n");

     }

 }

 bool valid_node(char ch){

     return strchr("-| #\n", ch) == NULL;  // we need add '\n' because fegets() will read the '\n' at end of each line to the tree.

 }

 void dfs_tree(int row, int col){

     printf("%c(", tree[row][col]);  // print root of the tree, and then print '('

     if(row < cur && tree[++row][col] == '|'){

         int i=col;

         row++;

         while(i -  >=  && tree[row][i-] == '-')i--; //  left bouder of "---"

         for(;tree[row][i] == '-'; i++)

             if(valid_node(tree[row+][i])) dfs_tree(row+, i);

     }

     printf(")");

 }

UVa 10562 Undraw the Trees 看图写树

啦啦啦，今天就到这里啦~改天见*★,°*:.☆(￣▽￣)/$:*.°★* 。

秒客网

UVa 10562 Undraw the Trees 看图写树

仰望高端玩家的小清新 http://www.cnblogs.com/luruiyuan/

相关文章