uva 10562 - Undraw the Trees

1955 ワード

少しdfsの感じで、木は連通していて、根ノードから葉まで追跡することができます.空の木のような特殊な状況には注意しなければならないことがあります.
 
#include<stdio.h>
#include<string.h>
#include<ctype.h>

#define MAX 210

char tree[MAX][MAX];
int idx;

void drawTree(int i, int j) {
	if (tree[i + 1][j] == '|') {
		printf("%c", tree[i][j]);
		tree[i][j] = '-';
		int s, t;
		for (s = j; tree[i + 2][s] == '-'; s--)
			;
		for (t = j; tree[i + 2][t] == '-'; t++)
			;
		s++;
		t--;
		printf("(");
		int p;
		for (p = s; p <= t; p++) {
			if (isprint(tree[i + 3][p]) && tree[i + 3][p] != '-'
					&& tree[i + 3][p] != '|' && tree[i + 3][p] != ' '
					&& tree[i + 3][p] != '#')
				drawTree(i + 3, p);
		}
		printf(")");

	} else {
		printf("%c()", tree[i][j]);
		tree[i][j] = '-';
	}

	return;
}

int main() {
	int cases;
	scanf("%d", &cases);
	while (cases--) {
		memset(tree, 0, sizeof(tree));
		idx = 0;
		while (gets(tree[idx]) != NULL ) {
			if (tree[idx][0] == '#')
				break;
			else
				idx++;
		}

		int i, j;
		int blank = 1;
		for (i = 0; i < MAX; i++) {
			for (j = 0; j < MAX; j++) {
				if (isprint(tree[i][j]) && tree[i][j] != '-'
						&& tree[i][j] != '|' && tree[i][j] != ' '
						&& tree[i][j] != '#') {
					blank = 0;
					printf("(");
					drawTree(i, j);
					printf(")
"); } } } if(blank) printf("()
"); } return 0; }