10562 - Undraw the Trees

[hpjhc]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

void dfs(int, int, int);
int k;
char s[300][300];

int main(void)
{
int n;
scanf("%d", &n);
while(n--)
{
k = 0;
while(1)
{
if(gets(s[k]), s[k][0] != '\0')
{
if(s[k][0] == '#')
break;
k++;
}
}
printf("(");
dfs(0, 0, k);
printf(")");
printf("\n");
}
return 0;
}

void dfs(int p, int low, int high)
{
int i, t1, t2;
for(i = low; i < high && i < strlen(s[p]); i++)
{
if(s[p] != ' ' && s[p] != '|' && s[p] != '#' && s[p] != '-')
{
printf("%c%c", s[p], '(');
if(p < k-1)
if(s[p+1] == '|')
{
t1 = 0;
while(s[p+2][t1] != '-')
t1++;
t2 = t1;
while(s[p+2][t2] == '-')
{
s[p+2][t2] = ' ';
t2++;
}
dfs(p+3, t1, t2);
}
printf(")");
}
}
}

[brianfry713]

Input:

Code: Select all

1
       A
       |
       -
       B
#

AC output:

Code: Select all

(A(B()))

[Darko]

Not sure why I even tried this - I have no idea what is wrong with my code. Sorry about the custom I/O, remnants of the old UVa... Also - I used dynamic array sizes, hence a lot of checks.

Code: Select all

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

public class Main {

	private static final int IN_BUFFER_SIZE = 1 << 16;
	private static final int OUT_BUFFER_SIZE = 1 << 16;
	private byte[] input = new byte[IN_BUFFER_SIZE];
	private int ix = IN_BUFFER_SIZE;
	private int bytesRead = ix;
	private byte[] output = new byte[OUT_BUFFER_SIZE];
	private int ox = 0;

	private void readMore() {
		try {
			bytesRead = System.in.read(input, 0, IN_BUFFER_SIZE);
			if (bytesRead <= 0)
				throw new RuntimeException();
			ix = 0;
		} catch (IOException e) {
			throw new RuntimeException();
		}
	}

	private void flushOut() {
		System.out.write(output, 0, ox);
		ox = 0;
	}

	private void append(char c) {
		if (ox == OUT_BUFFER_SIZE)
			flushOut();
		output[ox++] = (byte) c;
	}

	private String nextLine() {
		StringBuilder sb = new StringBuilder();
		while (true) {
			if (ix == bytesRead) {
				try {
					readMore();
				} catch (RuntimeException e) {
					if (sb.length() == 0)
						return null;
					else
						return sb.toString();
				}
			}
			char c = (char) input[ix++];
			if (c == '\r')
				continue;
			if (c == '\n')
				break;
			sb.append(c);
		}
		return sb.toString();
	}

	private int parseInt(String s) {
		int result = 0;
		int sign = (s.charAt(0) == '-') ? -1 : 1;
		if (sign == -1) {
			s = s.substring(1);
		}
		if (s.charAt(0) == '+') {
			s = s.substring(1);
		}
		int i = 0, max = s.length();
		if (max > 0) {
			while (i < max) {
				result *= 10;
				result += s.charAt(i++) - 48;
			}
		}
		return sign * result;
	}

	public static void main(String[] args) throws Exception {
		new Main().work();
	}

	/*
	 * SOLUTION BELOW
	 */

	class Node {
		int r, c;
		char label;
		List<Node> children;

		Node(int r, int c, char label) {
			this.r = r;
			this.c = c;
			this.label = label;
			children = new ArrayList<Node>();
		}
	}

	private void print(Node n) {
		append(n.label);
		append('(');
		for (Node child : n.children) {
			print(child);
		}
		append(')');
	}

	private Node go(int r, int c, int lim) {
		while (c < lim
				&& (t[r][c] <= ' ' || t[r][c] == '|' || t[r][c] == '-'
						|| t[r][c] == '#' || t[r][c] > '~'))
			c++;
		if (c == lim || used[r][c])
			return null;
		used[r][c] = true;
		Node ret = new Node(r, c, t[r][c]);
		if (r < n - 3 && t[r + 1].length > c && t[r + 1][c] == '|'
				&& t[r + 2].length > c && t[r + 2][c] == '-'
				&& t[r + 3].length > c) {
			int left = c;
			while (left > 0 && t[r + 2][left - 1] == '-'
					&& t[r + 1][left - 1] != '|' && !used[r + 3][left - 1])
				left--;
			int right = c;
			while (right < t[r + 2].length - 1
					&& t[r + 2][right + 1] == '-'
					&& (right + 1 >= t[r + 1].length || t[r + 1][right + 1] != '|'))
				right++;
			right++;
			if (right > t[r + 3].length)
				right = t[r + 3].length;
			while (left < right) {
				Node child = go(r + 3, left, right);
				if (child == null)
					break;
				ret.children.add(child);
				left = child.c + 1;
			}
		}
		return ret;
	}

	private int n;
	private char[][] t;
	private boolean[][] used;

	private void work() throws Exception {
		t = new char[256][];
		used = new boolean[256][];
		int nc = parseInt(nextLine().trim());
		while (nc-- > 0) {
			n = 0;
			String line;
			while ((line = nextLine()).charAt(0) != '#') {
				t[n] = line.toCharArray();
				used[n] = new boolean[t[n].length];
				n++;
			}
			append('(');
			if (n > 0) {
				Node root = go(0, 0, t[0].length);
				print(root);
			}
			append(')');
			append('\n');
		}
		if (ox > 0)
			flushOut();
		System.out.close();
	}

}

Can someone check the following I/O:
(Note that the last case is ambiguous, but nothing in the statement makes it illegal - it is the only reason why I mark nodes as 'used', otherwise some of them are shared children.)

Code: Select all

13
    A
    |
--------
B  C   D
   |   |
 ----- -
 E   F G
#
e
|
----
f g
#
       A
       |
       -
       B
#
$
|
-
%
|
-
^
|
-
&
|
---
! (
#
A
|
--
BC
#
  (
  |
------
) ( )(
| | ||
- - --
) ( )(
#
  A
 #|#
 ---
 #B#
#
A
#
A
|
--
BD
||
--
CE
 |
--
 F
 |
--
G 
#
A
|
---
BCD
|||
---
EFG
#
  A  
  |
-----
   B
#
A
|
--
AA
||
--
AA
 |
--
 A
 |
--
A 
#
A
|
---
BCD
| |
---
EFG
#

Code: Select all

(A(B()C(E()F())D(G())))
(e(f()g()))
(A(B()))
($(%(^(&(!()(())))))
(A(B()C()))
((()()())(((()))()())(((())))
(A(B()))
(A())
(A(B(C())D(E(F(G())))))
(A(B(E())C(F())D(G())))
(A(B()))
(A(A(A())A(A(A(A())))))
(A(B(E()F())C()D(G())))

[brianfry713]

AC output for your input:

Code: Select all

(A(B()C(E()F())D(G())))
(e(f()g()))
(A(B()))
($(%(^(&(!()(())))))
(A(B()C()))
((()()())(((()))()()(())(()()(())))
(A(B()))
(A())
(A(B(C()E(F(G())))D(C()E(F(G())))))
(A(B(E()F()G())C(E()F()G())D(E()F()G())))
(A(B()))
(A(A(A()A(A(A())))A(A()A(A(A())))))
(A(B(E()F()G())C()D(E()F()G())))