UVA10562解题报告

我的GitHub地址：https://github.com/DongChengrong/ACM-Program

仔细观察他给出的树，我们可以发现这棵多叉树长得比较有特点。最上是树根，而每一个节点只要有孩子下面就会跟着一个字符‘|’，我们可以根据这个特点来判断一个节点是否有孩子。如果有我们就继续捕捉他的子节点。如何将他的子节点一网打尽呢？我们有注意到所有的子节点的上方都有字符'-'，所以我们可以从这里做文章，先找到‘-’字符的最右边，在从这个位置依次往左寻找在'-'字符的下面是否有子节点

#include<cstdio>
#include<cstring>
#include<cctype>
using namespace std;

const int maxn = 200 + 10;

int n;
char buf[maxn][maxn];

void dfs(int r,int c)
{
    printf("%c(",buf[r][c]);
    if(r+1 < n && buf[r+1][c] == '|')
    {
        int pos = c;
        while(pos>=1 && buf[r+2][pos-1] == '-') pos--;
        for(;;pos++)
        {
            if(buf[r+2][pos]!='-' || buf[r+3][pos] == '\0') break;
            if(!isspace(buf[r+3][pos])) dfs(r+3,pos);
        }
    }
    printf(")");
}

void slove()
{
    n = 0;
    for(;;)
    {
        fgets(buf[n],maxn,stdin);
        if(buf[n][0] == '#') break;
        else n++;
    }

    printf("(");

    if(n)
        for(int i=0;i<strlen(buf[0]);i++)
            if(buf[0][i] != ' ') { dfs(0,i); break; }

    printf(")\n");
}

int main()
{
    int T = 0;
    fgets(buf[0],maxn,stdin);
    sscanf(buf[0],"%d",&T);
    while(T--) slove();
    return 0;
}