データ構造再帰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;
}