UVa 10562 - Undraw the Trees解题报告

发布时间:2017-1-23 16:26:29 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"UVa 10562 - Undraw the Trees解题报告",主要涉及到UVa 10562 - Undraw the Trees解题报告方面的内容,对于UVa 10562 - Undraw the Trees解题报告感兴趣的同学可以参考一下。

题意:根据图形化的树,输出前序遍历的节点。 思路:一开始我用边读边建的方法遍历,后来发现由于输入的两棵子树数据都在同一行,行不通。这道题的关键就在于处理"--------" 区间决定的子树。在网上看了一下,有人想到了根据‘————“区间进行扫描,因为每一层的节点都有上面一层的”——",根节点没有,但是我们可以自己构造。这一点很巧妙,我没有想到。 于是,根据上面的方法,我们用二维数组来存储整个树的原始数据,再初始化第一层上面的“——’区间。然后递归求解。 //10562 - Undraw the Trees #include <iostream> #include <cstring> using namespace std; char tree[210][210]; int high; void DFS(int x, int y); int main() { //freopen("data.txt", "r", stdin); int cases; scanf("%d", &cases); getchar(); while (cases--) { high = 1; while (cin.getline(tree[high], 210) && strcmp(tree[high], "#") != 0) high++; if(high == 1)//处理空树的情况 printf("()\n"); else { int len = strlen(tree[1]); for(int i = 0; i < len; i++)//初始化第一层的'-' tree[0][i] = '-'; printf("("); DFS(0, 0); printf(")\n"); memset(tree, 0, sizeof(tree)); } } return 0; } void DFS(int x, int y) { for(int i = y; tree[x][i] == '-'; i++)//根据节点上面的'-'来扫描 if(tree[x + 1][i] != ' ' && tree[x + 1][i] != '\0')//输出可打印字符 { printf("%c(", tree[x + 1][i]); if(x + 1 < high && tree[x + 2][i] == '|')//判断是否有子树 { int j; for(j = i; j && tree[x + 3][j - 1] == '-'; j--);//确定区间起点 DFS(x + 3, j); } printf(")"); } }

上一篇:ARM汇编指令
下一篇:在U-boot下实现自动识别启动Flash的原理(针对S3C24x0)(转自Tekkaman Ninja)

相关文章

相关评论