TopCoder problem "CircuitBoard" used in TCHS SRM 13 (Division I Level Three)



Problem Statement

    You've been given the task of designing part of a circuit board. You need to connect as many data lines as possible from the top edge of the board to the bottom edge of the board. However, there are a number of screwholes already in place that cannot be moved and will need to be avoided. layout will contain the current layout of the board, formatted like the example below, with '.' for open spaces and 'o' for screwholes: 



.o.ooo..
o.......
.....ooo
........
.o.oo...


The data lines must be kept short; this means they cannot go sideways or backwards on the board. They start at the top row, and at each step they must go either straight down, down and one cell to the right, or down and one cell to the left. Two data lines cannot occupy the same cell. In the example above, we can fit in 3 data lines by laying them out like this: 



\o|ooo/.
o||../..
./|.|ooo
|.|.\...
|o|oo|..


Return the maximum number of complete data lines that can be placed on the board.
 

Definition

    
Class:CircuitBoard
Method:maxDataLines
Parameters:String[]
Returns:int
Method signature:int maxDataLines(String[] layout)
(be sure your method is public)
    
 

Constraints

-layout will contain between 1 and 50 elements, inclusive.
-Each element of layout will contain between 1 and 50 characters, inclusive.
-Each element of layout will contain the same number of characters.
-Each element of layout will contain only the characters '.' or lowercase 'o'.
 

Examples

0)
    
{
".o.ooo..",
"o.......",
".....ooo",
"........",
".o.oo..."}
Returns: 3
The example from the problem statement.
1)
    
{
".......",
"oo...oo",
".oo.oo.",
"oo...oo",
"......."}
Returns: 1
Two data lines cannot occupy the same cell, so watch for bottlenecks.
2)
    
{
"oooooooooo.....",
"...............",
"...............",
"...............",
".......oooooooo"}
Returns: 1
You can't go sideways or backwards (only straight down or diagonal) - so in this case only one wire can reach from the top right to the bottom left.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6541

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10065&pm=6541

Writer:

jmzero

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Greedy, Search