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 String[], 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: | String[], int | | Returns: | int | | Method signature: | int solve(String[] grid, int unfoldLimit) | | (be sure your method is public) |
|
| |
|
| |
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 | |
|