Connection Status:
Competition Arena > DrawingPointsDivTwo

DrawingPointsDivTwo

SRM 560 · 2012-06-05 · by meret

SRM 560 · 2012-06-05 · by meret · Simple Search, Iteration
Class Name: DrawingPointsDivTwo
Return Type: int
Method Name: maxSteps
Arg Types: (vector<string>)
Problem Statement

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.

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
0)
{"*..*"}
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.

1)
{"...",".*."}
Returns: -1
2)
{"*.*"}
Returns: 0
3)
{"..*.",
 "*...",
 "...*"}
Returns: 1
4)
{"....................",
 "..........*.........",
 "....................",
 ".........*..........",
 "....................",
 "....................",
 "....................",
 "....................",
 "....................",
 "....................",
 "....................",
 "....................",
 ".*..................",
 "....................",
 "*.............**....",
 "....................",
 "....................",
 "................*...",
 "....................",
 "...................."}
Returns: 11

Submissions are judged against all 117 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class DrawingPointsDivTwo with a public method int maxSteps(vector<string> points) · 117 test cases · 2 s / 256 MB per case

Submitting as anonymous