TopCoder problem "FiveStarPatterns" used in TCHS SRM 29 (Division I Level Three)



Problem Statement

    

Starting with an empty grid (empty spaces denoted by '.'), you must create the pattern shown in layout by adding lines of 5 '*' characters. Lines may be horizontal or vertical, must stay completely within the grid, and may overlap. Here is an example pattern:


.*....
.*****
.*....
*****.
.*....

This pattern would require 2 horizontal lines and 1 vertical line, for a total of 3 lines. The grid will not be taller than 5 rows or wider than 10 columns. Return the minimum number of lines required to create the pattern shown in layout. If a given pattern cannot be created, return -1.

 

Definition

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

Constraints

-layout will contain between 1 and 5 elements, inclusive.
-Each element of layout will contain between 1 and 10 characters, inclusive.
-Each element of layout will contain the same number of characters.
-Each element of layout will contain only '.' and '*' characters.
 

Examples

0)
    
{
".*....",
".*****",
".*....",
"*****.",
".*...."
}

Returns: 3
The example from the problem statement.
1)
    
{
"...*****..",
"..*******.",
".*********"
}
Returns: 5
Note that the lines can overlap. The above example is all horizontal lines: 1 for the first row, 2 for the second row, and 2 more for the third.
2)
    
{
"......",
".****.",
".****.",
".****.",
".****."
}
Returns: -1
You can't draw lines shorter than 5 '*'s, so there's no way to make this pattern.
3)
    
{
"**********",
"**********",
"**********",
"**********",
"*********."
}
Returns: 10

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10653&pm=6583

Writer:

jmzero

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Dynamic Programming, Greedy