PROBLEM STATEMENT
NOTE: This problem statement contains images that may not display properly if viewed outside of
the applet.
You are given a white rectangular grid made up of square cells. Some cells contain black squares,
and some contain black squares that have been folded in half to form right triangles, such that
one of their sides matches the grid line to the right of the cell and another side of the triangle
matches the grid line to the bottom of the cell. At most unfoldLimit of these triangles can be
unfolded to become black squares. However, black squares cannot be folded to become triangles.
We are interested in forming the largest possible proper black triangle in the grid using the
aforementioned operations. A black triangle is considered proper within a grid configuration if
no other black shape shares a line segment with it. However, black shapes may still share one or
more points with the triangle. The size of a triangle is defined as the number of grid cells that
are currently occupied by the triangle.
The grid will be given as a vector , where the j-th character of the i-th element
represents the cell at row i, column j. '.' represents an empty cell, '#' represents a cell
containing a black square, and '/' represents a cell containing a black triangle. Return the
largest possible size for a proper triangle that can be formed in the given grid by unfolding at
most unfoldLimit triangles. In case it is not possible to form a proper black triangle in the
grid, return -1.
For example, consider the following input grid:
If unfoldLimit is greater than or equal to 3, the largest possible proper triangle size is 10:
If unfoldLimit is 2, the largest possible proper triangle size is 3:
Larger black triangles are possible, but they would not be proper triangles.
DEFINITION
Class:UnfoldingTriangles
Method:solve
Parameters:vector , int
Returns:int
Method signature:int solve(vector grid, int unfoldLimit)
CONSTRAINTS
-grid will contain between 1 and 50 elements, inclusive.
-Each element of grid will contain between 1 and 50 characters, inclusive.
-Each element of grid will contain the same number of characters.
-Each character in grid will be '.', '#' or '/'.
-unfoldLimit will be between 1 and 2500, inclusive.
EXAMPLES
0)
{".../",
"../#",
"./#/",
"/#//"}
4
Returns: 10
1)
{".../",
"../#",
"./#/",
"/#//"}
2
Returns: 3
Examples 1 and 0 were explained in the problem statement.
2)
{"////",
"////",
"////",
"////"}
5
Returns: 6
3)
{".....#...",
"....###.."}
10
Returns: -1
4)
{"#//#",
"#//#",
"####",
"///#"}
4
Returns: 1
5)
{".../.../",
"../#..//",
"./.#.///",
"/###...."}
3
Returns: 6
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)2010, TopCoder, Inc. All rights reserved.