TopCoder problem "RotatingTriangles" used in SRM 444 (Division II Level Three)

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. Each of these triangles can be rotated left or right by any multiple of 90 degrees. They can also be unfolded to become squares. However, black squares cannot be folded to become triangles.

Your task is to generate proper black triangles 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 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 total number of distinct proper black triangles that can be formed in this grid. Two triangles are considered distinct if they differ in at least one vertex.

For example, consider the following input grid:

It is possible to generate 5 distinct proper black triangles:



Method signature:int count(String[] grid)
(be sure your method is public)


-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 '/'.


Returns: 10
Returns: 5
This is the example from the statement.
Returns: 0
Returns: 46

Problem url:

Problem stats url:




PabloGilberto , Yarin , Andrew_Lazarev , ivan_metelsky

Problem categories:

Dynamic Programming, String Manipulation