DrawingPointsDivTwo | Topcoder Archive

Problem Statement

This problem statement contains images. It may not display properly outside the applet.

Once upon a time, Little Wojtek had drawn a number of points with integer coordinates onto a sheet of paper. Then he made zero or more steps. Each step looked as follows: Let's call all the points on Wojtek's paper old points. For every four old points that formed the vertices of a 1x1 square, Wojtek would draw a point in the middle of that square. Once he had drawn all such new points, he took an eraser and erased all the old points.

An example is shown in the picture below. On the left is Wojtek's original paper. In the middle is the same paper with the new points filled in. (For clarity, the old points are black and the new ones are red.) On the right is the paper after the old points were erased.

He has been playing for a while when he was called downstairs to dinner. He looked at the paper with a surprised face and wondered how many steps he had made.

You are given a String[] points, describing a rectangular area of Wojtek's paper. This area contains all of the points that were drawn by Wojtek at the end of his play. More precisely, you may assume that there are real numbers (not necessarily integers) dy and dx such that the following holds:

If points[i][j] = '*', then there is a point at coordinates (dx+j,dy+i).
There are no other points anywhere on the paper, only those that follow from the previous statement.

Return the maximum number of steps Wojtek could have made. If there is no maximum (that is, if the number of steps can be arbitrarily large), return -1 instead.

Definition

Class:: DrawingPointsDivTwo
Method:: maxSteps
Parameters:: String[]
Returns:: int
Method signature:: int maxSteps(String[] points)
(be sure your method is public)

Notes

Note that the points drawn by Wojtek in the last step of his play could have non-integer coordinates.
The paper used by Wojtek could have been arbitrarily large. In other words, ignore the paper size, it does not limit the number of steps in any way.

Constraints

points will contain between 1 and 20 elements, inclusive.
points[0] will contain between 1 and 20 characters, inclusive.
All elements of points will contain the same number of characters.
Each character of each element of points will be either '*' (an asterisk) or '.' (a period).
points will contain at least one '*' character.

Examples

```
{"*..*"}
```
```
Returns: 1
```
An example scenario: Wojtek draws the initial points at locations (100, 100), (100, 101), (101, 100), (101, 101), (103, 100), (104, 100), (103, 101), (104, 101), (315, 714). In the first and only step, Wojtek draws points at locations (100.5, 100.5) and (103.5, 100.5). These locations correspond to points in this test case.
```
{"...",".*."}
```
```
Returns: -1
```
```
{"*.*"}
```
```
Returns: 0
```
```
{"..*.",
 "*...",
 "...*"}
```
```
Returns: 1
```

{"....................",
 "..........*.........",
 "....................",
 ".........*..........",
 "....................",
 "....................",
 "....................",
 "....................",
 "....................",
 "....................",
 "....................",
 "....................",
 ".*..................",
 "....................",
 "*.............**....",
 "....................",
 "....................",
 "................*...",
 "....................",
 "...................."}

Returns: 11

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)2024, Topcoder, Inc. All rights reserved.