OddEvenTree | Topcoder Archive

Problem Statement

In a tree, the distance between two nodes is the number of edges on the (only) simple path that connects them.

You are given a String[] x with N elements, each containing N characters. Draw a tree with N nodes, numbered 0 through N-1. The tree must have the following properties: For each i and j, if x[i][j] is 'E' the distance between i and j must be even, and if it is 'O' (uppercase o) this distance must be odd.

If there is no tree with these properties, return {-1}. Otherwise, return a int[] with 2N-2 elements: the list of edges in one such tree. For example, if N=3 and your tree contains the edges 0-2 and 1-2, return {0,2,1,2}. If there are multiple correct outputs you may output any of them.

Definition

Class:: OddEvenTree
Method:: getTree
Parameters:: String[]
Returns:: int[]
Method signature:: int[] getTree(String[] x)
(be sure your method is public)

Notes

If you use plugins to test your solution, be careful. Plugins cannot tell you whether your solution is correct -- they'll just tell you whether it matches the example output exactly.

Constraints

n will be between 2 and 50, inclusive.
x will contain exactly n elements.
Each element in x will have exactly n characters.
Each character in x will be 'O' or 'E'.

Examples

{"EOE",
 "OEO",
 "EOE"}

Returns: {0, 1, 2, 1 }

The tree: 0-1-2 is a valid answer.

```
{"EO",
 "OE"}
```
```
Returns: {0, 1 }
```
```
{"OO",
 "OE"}
```
```
Returns: {-1 }
```
dist[0][0] must be 0, and it should be an even number, so it is impossible.
```
{"EO",
 "EE"}
```
```
Returns: {-1 }
```
dist[0][1] should be same with dist[1][0].

{"EOEO",
 "OEOE",
 "EOEO",
 "OEOE"}

Returns: {0, 1, 0, 3, 2, 1 }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.