データ構造再帰uva 1052-Undaw the Trees

2132 ワード


テーマリンク:
http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&Itemid=8&page=show_problem&problem=1503
 
タイトルの大意:
与えられた形の木を別の形の木に出力します。
 
問題解決の考え方:
再帰的に木を建てる過程を模擬して、木を建てながら出力します。
 
コード:
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#define eps 1e-6
#define INF (1<<20)
#define PI acos(-1.0)
using namespace std;


int sumrow;
char save[220][220];  //        

bool notin(char a) //      
{
    if(a!='-'&&a!=' '&&a!='#'&&a!='|'&&a)
        return true;
    return false;
}

void dfs(int row,int column)
{
    putchar(save[row][column]); 

    if(save[row+1][column]!='|') //    
    {
        printf("()");
        return ;
    }

    //     
    int left,right;
    
    putchar('(');
    left=right=column;
    while(save[row+2][--left]=='-') //    '-'    
    ;
    left++;

    while(save[row+2][++right]=='-') //    '-'    
    ;
    right--;

    for(int i=left;i<=right&&i<strlen(save[row+3]);i++)
        if(notin(save[row+3][i]))
        {
            dfs(row+3,i);
        }
    putchar(')');
    return ;

}

int main()
{
    int ca;

    scanf("%d",&ca);
    getchar();

    while(ca--)
    {
        sumrow=0;
        memset(save,0,sizeof(save)); 

        while(gets(save[++sumrow])&&save[sumrow][0]!='#')
        ;

        sumrow--;
        if(sumrow==0)  //         ,  ,wa    
        {
            printf("()
"); continue; } for(int i=0;i<strlen(save[1]);i++) // 。 if(notin(save[1][i])) { putchar('('); dfs(1,i); putchar(')'); } putchar('
'); } return 0; }