Statistics

Problem Statement for "DrawingPointsDivTwo"

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

  1. {"*..*"}

    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.

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

    Returns: -1

  3. {"*.*"}

    Returns: 0

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

    Returns: 1

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

    Returns: 11

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

    Returns: -1

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

    Returns: 0

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

    Returns: 3

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

    Returns: 4

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

    Returns: 3

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

    Returns: -1

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

    Returns: 1

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

    Returns: 10

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

    Returns: 4

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

    Returns: 1

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

    Returns: 0

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

    Returns: -1

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

    Returns: 3

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

    Returns: 6

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

    Returns: -1

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

    Returns: -1

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

    Returns: 0

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

    Returns: 1

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

    Returns: -1

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

    Returns: 0

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

    Returns: 4

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

    Returns: 5

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

    Returns: 2

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

    Returns: 0

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

    Returns: -1

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

    Returns: -1

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

    Returns: 3

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

    Returns: 8

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

    Returns: -1

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

    Returns: 4

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

    Returns: 2

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

    Returns: 0

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

    Returns: 7

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

    Returns: 1

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

    Returns: 4

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

    Returns: -1

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

    Returns: 2

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

    Returns: 1

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

    Returns: 8

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

    Returns: -1

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

    Returns: 2

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

    Returns: 1

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

    Returns: 15

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

    Returns: 1

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

    Returns: -1

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

    Returns: 3

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

    Returns: 1

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

    Returns: 0

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

    Returns: 0

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

    Returns: 4

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

    Returns: 0

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

    Returns: -1

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

    Returns: 8

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

    Returns: -1

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

    Returns: 17

  61. {"....**...*.*.."}

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

  91. {"*"}

    Returns: -1

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 1

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

    Returns: 0

  99. {".*..*.*.**.."}

    Returns: 0

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

    Returns: -1

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: -1

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

    Returns: -1

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

    Returns: 0

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

    Returns: -1

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

    Returns: 11

  112. {"*.*" }

    Returns: 0

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

    Returns: 2

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

    Returns: -1

  115. {"**" }

    Returns: -1

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

    Returns: 4

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

    Returns: -1

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.
This problem was used for: