## 10562 - Undraw the Trees

Moderator: Board moderators

hpjhc
New poster
Posts: 17
Joined: Wed Jun 26, 2013 10:35 am

### 10562 - Undraw the Trees WA

#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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10562 - Undraw the Trees WA

Input:

Code: Select all

``````1
A
|
-
B
#
``````
AC output:

Code: Select all

``(A(B()))``
Check input and AC output for thousands of problems on uDebug!

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am

### Re: 10562 - Undraw the Trees

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 byte[] output = new byte[OUT_BUFFER_SIZE];
private int ox = 0;

try {
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) {
try {
} 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;
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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10562 - Undraw the Trees

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())))
``````
Check input and AC output for thousands of problems on uDebug!