Statistics

Problem Statement for "EllysFlags"

Problem Statement

Elly has a white sheet of squared paper with several rows and columns. While she was mostly ignoring the teacher in a rather boring class, the girl colored random squares with green and red. At some point she realized that the paper was full of Bulgarian flags! The girl says she has drawn a "flag" if three consecutive squares going only down and to the right (each sharing a side with the next one) are, in this order, white, green and red. Thus, there are four types of flags:


Please note that several flags can share cells. For example, in the following configuration there are a total of six flags, three of which start from the white square in the top left corner:


Fascinated by what she has unconsciously done, she now wants to fill some of the remaining white squares with green and red, such that the number of "flags" in the end is as large as possible.
The current coloring of Elly's paper will be given to you in the String[] paper. paper[row][col] will be 'W' if the square at (row, col) is white, 'G', if it is green, and 'R', if it is red. Return the maximum number of flags that can be drawn if the girl fills some (possibly none) of the remaining white cells with green and red optimally.

Definition

Class:
EllysFlags
Method:
getMax
Parameters:
String[]
Returns:
int
Method signature:
int getMax(String[] paper)
(be sure your method is public)

Notes

  • The paper cannot be rotated in any way.
  • The girl can only change white squares to either green or red. No square which is already colored can become white or be re-colored.

Constraints

  • paper will contain between 1 and 10 elements, inclusive.
  • Each element of paper will contain between 1 and 10 characters, inclusive.
  • All elements of paper will have the same length.
  • Each character in paper will be 'W', 'G' or 'R'.

Examples

  1. {"WGWWR", "GRGRG", "RWGRW", "GGWGR"}

    Returns: 9

    This is the example from the problem statement. Currently, there are 6 flags already drawn. We can color the square on the first row, fourth column in green, obtaining two additional flags. Additionally, if we color the cell on the fourth row, third column in red, we lose one of the flags we had before, but we get two new ones.

  2. {"WWGRWW", "WWWWWW", "WWRGWW"}

    Returns: 13

  3. {"WWGGRGWGGW", "WWRWRGWWRG", "GGWRWRRWRW", "WWRRWWWWGR", "WWGWWGRWGR", "WWGWRRWWWR", "WRGWWGWGWW", "WWRGWRWGGW", "WWRRWWGWRW", "WRGWRRRGWW"}

    Returns: 42

    The answer is 42.

  4. {"WWWWWWW", "WWWWWWW", "WWWWWWW", "WWWWWWW", "WWWWWWW", "WWWWWWW", "WWWWWWW", "WWWWWWW"}

    Returns: 56

    No restrictons on this paper - every cell can be colored in any color.

  5. {"W"}

    Returns: 0

  6. {"WW", "WW"}

    Returns: 2

  7. {"WWWWWWWRWW"}

    Returns: 2

  8. {"W", "W", "W", "W", "W", "W", "W", "W", "G", "W"}

    Returns: 3

  9. {"WWWWWWWWWW", "WWWWWWWWWW", "WWWWWWWWWW", "WWWWWWWWWW", "WWWWWWWWWW", "WWWWWWWWWW", "WWWWWWWWWW", "WWWWWWWWWW", "WWWWWWWWWW", "WWWWWWWWWW"}

    Returns: 108

  10. {"GGGGGGGGGG", "GGGGGGGGGG", "GGGGGGGGGG", "GGGGGGGGGG", "GGGGGGGGGG", "GGGGGGGGGG", "GGGGGGGGGG", "GGGGGGGGGG", "GGGGGGGGGG", "GGGGGGGGGG"}

    Returns: 0

  11. {"RRRRRRRRRR", "RRRRRRRRRR", "RRRRRRRRRR", "RRRRRRRRRR", "RRRRRRRRRR", "RRRRRRRRRR", "RRRRRRRRRR", "RRRRRRRRRR", "RRRRRRRRRR", "RRRRRRRRRR"}

    Returns: 0

  12. {"WWWWWWWW", "WWWWWWWW", "WWWWWWWW", "WWWWWWWW", "WWWWWWWW", "WWWWWWWW", "WWWWWWWW"}

    Returns: 56

  13. {"WWWWWWWW", "WWWWWWWW", "WWWWWWWW", "WWWWWWWW", "WWWWWWWW", "WWWWWWWW", "WWWWWWWW", "WWWWWWWW", "WWWWWWWW", "WWWWWWWW"}

    Returns: 84

  14. {"RGGGWW", "WWRGWG", "GRWWWW", "GWRWGW", "WWRWWW", "WGWWWW", "RWRWGG", "WGGWRW"}

    Returns: 19

  15. {"WWWWWWWWW", "WWWWWWWWW", "WWWWWWWWW", "RWRWRWRWW", "WWRWWWWWW", "WWWWWWWWW", "WWWWWWWWG", "WWWWWWWWW", "WWWWWWWGW"}

    Returns: 75

  16. {"WWWWRWGW", "WWWWGWRW", "WWRWWWRG", "WWRWWGRW", "RWWWWWWG", "WWWWWGGW", "WWGWWWGR", "RWGWWWWG", "WGWRWWWW", "WGWWRGWW"}

    Returns: 50

  17. {"WWRRWWWGWG", "GRRWRGWWRW", "WWWWWWWWWG", "WGWWWGWGGW", "WGGRWWWWWW", "WGWWWWWRRW", "WWWRWWWWWR", "WRRRRWGGGW"}

    Returns: 47

  18. {"RWWWGWWWW", "WRWRWRRRW", "WRWWWGWWG", "WGWGWRWWG", "WWWWGGRWW", "WWGRRWGWW", "GWWWGWWWW", "RRWGWWWWR", "WWWWWWWWW", "WWWWWWWWW"}

    Returns: 55

  19. {"WRWWWGWRWW", "WWRGWWWGWW", "WWRWWRGWWR", "RRRWGRWWRW", "WRWWGRWWWW", "WWWWWRWWWW", "RRWWWWWWWG", "WWWGWWRRWR", "WWRGWWWWWW"}

    Returns: 52

  20. {"GWWRWWRWWW", "WRRWGWWWWW", "GRWGWWWWGW", "RWRWWRRWWR", "GWRWWWRGWW", "WWWWRWWWGW", "WRWWWWWWWW", "WWWWWWRWWW", "GGWGWWGWWW", "WWWWWGGWWG"}

    Returns: 70

  21. {"WGWWWWWGWW", "WWRWWWWRWW", "WGRWWWWWRW", "RGGRWWWWWW", "WWWWWRWWWW", "WWWGWGWRWG", "WWWWWWWWWW", "WGGWWWWWGW", "WWRWWWWWGW", "WRWWWWGGGW"}

    Returns: 67

  22. {"WWWWGWRWWR", "RWRRRRRRWR", "GWGRRRWRWR", "RGRRWGRGRR", "RGRGRRRRRR", "GRRGGRRRGR", "WRRWRWRRGR", "RRRRGRWRRG", "GWWRRGWGWR", "RRRRRRRRWG"}

    Returns: 16

  23. {"WWWWWWWWWW", "RRWWGWWWWW", "WRWGGRGWWR", "WWRWWWWGWW", "WWWWGWRWWW", "WGWWWWWRWW", "WWGWWWWGWW", "WWWWWRWRWW", "WWWWRWGWWW", "WWWWWWWWWW"}

    Returns: 74

  24. {"RWRRRRRGGR", "WGGWRGWWRR", "WRRWRRGWWW", "WWRGGWWRRR", "WGWRGRGRWW", "WWRWWWRGGW", "RWWWGRGGGG", "WWGRRRWRRW", "RWRRWWWWGW", "RRGRWGRWWR"}

    Returns: 39

  25. {"WGRGGWGGRR", "GRGRGGRRRW", "GWRWGRWRGW", "GRWGGWGGRW", "GRRGGRWGGG", "RGRRRWWGWG", "RGWGGRWGGG", "RGWWGWWRGG", "GWGWWGRGWW", "WRRWWWWWWG"}

    Returns: 28

  26. {"GGGGRGWGWW", "GGWRWWWGWW", "WWRRGWWRWW", "RRWGWWGRGG", "RGGGRRGWWR", "WGWWGGGRWW", "WGRRGGWWGG", "GRGGGWGRRW", "WWGWWRGWGG", "RWGRWGGGGR"}

    Returns: 28

  27. {"WWRGWGRWWR", "GWWRRWWWRR", "RRWRRGRWRR", "WRGGRWWWWG", "RRWWWRRWRW", "WRRWRRGWRR", "WRWWRRRWWG", "WRRWRWRWWW", "RRRWWRRWWR", "RWRRRRGWRW"}

    Returns: 35

  28. {"GWWWWWWWWW", "GGWWWWWGGW", "WWWGGWWWGW", "WWGWWGGWWG", "GWWGGWWWWW", "GWWWGWGGWG", "GWWGWGWWWG", "WWGGWWWGWW", "WWWGWWWWWW", "WWGGWWGWGG"}

    Returns: 57

  29. {"RWWWRWWRRW", "RWWRRWRWRW", "WWWRWWRWWW", "RRRWWWRWWR", "WWRRRWWWWW", "RWWWWRWWWR", "WRRWRWRWRR", "RRWWWWWWWW", "RRRWWRWWWR", "WWRRWWWRWW"}

    Returns: 56

  30. {"WWWWWWWWRW", "WWWRWWWWWW", "WWWWWWGWWW", "WWWWWWWWWW", "WWWWWWWWWW", "WWWWWWWWWW", "WWWWWWWWWW", "WWWWWWWWWW", "WWGWWWWWWW", "WWWWWWWWWW"}

    Returns: 100

  31. {"WWWWWWWWWW", "WWWWWWWWWW", "WWWWWWWWWG", "WRGWWWWWWW", "WWWWWWWWWW", "WWWWWWWWWW", "WWWWWWWWWW", "WWWWWWWWWW", "WWWRWWWWWW", "WWWWWWWWWW"}

    Returns: 100

  32. {"WGWWWWWWWW", "WWGWWWWGWW", "WWGWWWWWWW", "WWWWGWWWWW", "RWWWGWWRWW", "WWWWWWWWGW", "WWWGWWWRWW", "WWWWWWWWWW", "WWGWWGWWWW", "WRWWWWWWGW"}

    Returns: 82

  33. {"RWWWWWWRWR", "RWWWRWWWRW", "WWWWRWRWWW", "WWWWWWWWRW", "WWRWWWWWWW", "WGWWWWWWRW", "WWGRWWWWWW", "WWGWWWRRWW", "WWWWWWWWWW", "WWWWWWRWWR"}

    Returns: 73

  34. {"GRWRWGWRWG", "WGGWWGGWRG", "WGRGGRWGWR", "WGGGRWGGWG", "GRGGWGWGGR", "WWWRRGWGGR", "RWGRRRGGRW", "WRGWWGWWWG", "GGGWGWRWWW", "WRWWGGWGWG"}

    Returns: 34

  35. {"WGGGRWRRWG", "GGWWRWRWRW", "GWRWRRGRRG", "RWRRWRWRRR", "RRWWGRGGRG", "GGGRRGRRGG", "GRWGWGRRRR", "GRGRGRWWGG", "GRGRGRGWRR", "GRWRRGRRRR"}

    Returns: 22

  36. {"GRWRGGWGWR", "RGGRRRGGGG", "WRRGRRGGGR", "RGRGGGGGWG", "GWRRRRGGWR", "WRGRRGRRRG", "RRGRGWRRRR", "RRWRGRWGGG", "GGRRRGGWRR", "RRGGGRRGGR"}

    Returns: 9

  37. {"GRGRRGRGWW", "RRRRRGGGRG", "RGGRRGGGGG", "RRGRWGRWGG", "RGGGGGRGGR", "GRRGGGGWGR", "RGRRRRRRGR", "RRRRRRWGGG", "GGRGRGGGGR", "RRRRRGRRRR"}

    Returns: 3

  38. {"GGRGGGGGRG", "GGGRRGRGGR", "GRGGGGGRRG", "RRRGRRRGRR", "GGGGRGRGRG", "GGGGRGRRRG", "GRRGRRGGGG", "GRGRRGRGGG", "RRRGRGRGGG", "GGGRGGGRRG"}

    Returns: 0

  39. {"GWWGGGRWGR", "WGGGWGWGGG", "GGGGWWGGRG", "GRGGWGWGRG", "GGGWWWGWGW", "WWRWRRRWGG", "GWWWGRRGWG", "WGRGGGWWWW", "WGGGWGWWGW", "WRGGGWWWGW"}

    Returns: 32

  40. {"GWRWWWWWWR", "GWGWRWRWRR", "RRWWRWRGRW", "WWRWRRRWRG", "RRRRRRRWWR", "RWGRGRWWWR", "WGRGGWGRRR", "RRGWRRWRWR", "RGRRWRRRWG", "WRWGRRRWWW"}

    Returns: 36

  41. {"RGWRGW", "GGGWRG", "GGWGGR", "WGWRWW", "GWWRGG"}

    Returns: 7

  42. {"W", "W", "G", "G", "W", "W", "R"}

    Returns: 1

  43. {"WG", "RG", "GW", "WR", "GG", "WR"}

    Returns: 1

  44. {"RWWRRGR", "RWRWRRR", "RWWRWRR"}

    Returns: 4

  45. {"RWW", "RRR", "GWG", "RGR", "GWR", "RRG", "GGR"}

    Returns: 4

  46. {"WWGWWRW", "WWWWGRR", "WRWWRGW"}

    Returns: 13

  47. {"GWWWGWG", "GWWGWWG", "WWWGWWR", "WWWWWWW", "WGWWWGW", "WWWWGRW"}

    Returns: 27

  48. {"WWW"}

    Returns: 1

  49. {"GWR", "GGG", "WWG", "GGG"}

    Returns: 1

  50. {"GGGRGGRWWG", "GGGRGGRRRG", "RRRGRRRGGW", "RGRGGGGGGW"}

    Returns: 1

  51. {"GWWGWWGWWW", "GWGWWGGWGW", "WWWGWWWWWW", "WGGGWWGWGW", "GGWGGWWGGG", "WWWGWGGGWW", "WGWGGWGWWW"}

    Returns: 37

  52. {"GWWRWRG", "WRRGWWW", "GWWRWWG", "GWWWWWW"}

    Returns: 11

  53. {"GRGGRRRRGW", "GGWWWWGRRR", "GWRWGWWWRR", "WRWGWRGRWR"}

    Returns: 10

  54. {"RRWWR", "GRWWR", "RGRRG", "WRGWR", "RRRRW", "GGGGW", "WRRWW", "RRRWG", "RRGRG"}

    Returns: 6

  55. {"RWWWRR", "RRGWRW", "RWWGRR", "GWWRGW", "RRGRWW"}

    Returns: 7

  56. {"WWWWWW"}

    Returns: 2

  57. {"RRGGWWWG", "RWRRRGGW", "GWRRGRRR", "GGWRRGWG", "WGRGRGGG", "WRGGWGRG"}

    Returns: 10

  58. {"RGWRGGGGRG", "GGWRGGGGRG"}

    Returns: 1

  59. {"GRR", "WRW"}

    Returns: 0

  60. {"RWWWWWRWW"}

    Returns: 2

  61. {"R", "R", "G", "W"}

    Returns: 0

  62. {"WWWWWGWGWW", "GGWWRWWWGG", "WRWWWWWGWW", "WWWWGWGGWG", "RWWWWWWWGW", "WGGGWWGWGR", "RWRWWWWWGG", "WGWWRGWWWR", "RWGWGRRWGW", "RWGWGRWWWW"}

    Returns: 57

  63. {"RWW", "WWG", "RRG", "RWG", "GWW", "WGW"}

    Returns: 5

  64. {"WW", "WR"}

    Returns: 2

  65. {"WWW", "WWW", "WWR", "WWW", "WWG", "WRW", "WWW", "WWW", "WWW"}

    Returns: 18

  66. {"WGR", "WWW", "GWG", "WWG"}

    Returns: 5

  67. {"GG", "GG", "WG"}

    Returns: 0

  68. {"GWWW", "WWWW", "WWGW", "WWWW", "WGWW"}

    Returns: 13

  69. {"RWRRGWGGW", "WWGRWWWWW", "GWWWWWWRR", "WWWWWWWGW", "WGWWRWWRW", "RGGWWRWWW", "RRWWWWGWW"}

    Returns: 34

  70. {"GGGRG", "WWGWR", "GGRGW", "RRGRG"}

    Returns: 6

  71. {"WRWWWRWWW"}

    Returns: 2

  72. {"GWRGWWRGRG", "RWGGGRGGGW", "GRRRRRGGRG", "WGGWRGGWWW", "GRRRRRGGGG", "WGRGGRWWRR", "WRWGGGRWWG"}

    Returns: 14

  73. {"WWWWGWGGGR", "WRWGRWGWGG", "GGGWWGGWGR", "WGGGWWWGRW", "GGGGWGGWGG", "RWWWWGWWWW"}

    Returns: 28

  74. {"GGRRRG", "GGGRRW", "RGRWWR", "RGWRRR", "WRRRWR", "WWGRWR", "WRRWGR", "RRWWRR"}

    Returns: 12

  75. {"RWGWRGR", "GRRRRRG", "RRRWWWG", "RWRWWRW"}

    Returns: 5

  76. {"WWWWRWRRWW", "WWRRRWRGRW", "WWRWRRWWRR", "RRRWRRRRWW", "WWRWRGWRRR"}

    Returns: 17

  77. {"GWRWR", "WWGWG", "WGGWG", "WWWWW", "WGGWW", "WWWWW", "GGGRW", "GWWWG"}

    Returns: 16

  78. {"WWR", "WWW", "RWW", "WWW", "WGR", "WRW"}

    Returns: 11

  79. {"WWWWWWWG", "WWWWWWWW", "WWWGWWWW", "WWWWWWGW", "WWWWWWWW", "WWWWWWRW", "WWWWWWGR", "WGRGWWWW", "WWWWWWWW", "WWWWGWWW"}

    Returns: 67

  80. {"WWRWGWWRW", "RWGWGRWWW", "WRGWGRWWR"}

    Returns: 10

  81. {"RWWRWRRGGW", "RRWRGWWRWR", "GWRWGGGWRG", "WWGGWGGGWG", "WRWGWRRGWW", "WRWRRWGWRR", "WGWRWWRGGG", "GRRGRWWWGG", "WWRWGRWWWR"}

    Returns: 31

  82. {"WWW", "WWW", "WRR", "RRW", "WWR", "RWR", "WWR", "WWW"}

    Returns: 13

  83. {"R"}

    Returns: 0

  84. {"GGG", "GGR", "WWW"}

    Returns: 1

  85. {"WWWR", "WWWR", "RRWW", "RWWW", "RWGR"}

    Returns: 10

  86. {"WGG", "WGW", "RWW", "GWG", "GGG", "WGG"}

    Returns: 2

  87. {"GWGWGWRWW"}

    Returns: 1

  88. {"RW"}

    Returns: 0

  89. {"GGRR", "GRRW", "WGWG", "RRWG", "RRGW", "GGRW"}

    Returns: 5

  90. {"WWWWWW"}

    Returns: 2

  91. {"WW", "GW"}

    Returns: 2

  92. {"WWGRW", "WWGGG", "GGGGW", "WWGWR", "WWWWW", "WRRGW", "GGGRW", "GGGWG", "WGGGW", "GRRGG"}

    Returns: 18

  93. {"WRWWWWWWW", "WWRWWWRWW", "WGRRWWWGW", "GWWWGWWWW", "WWGGWWWWR", "WWGGWWWWW", "WWWWWWWWW", "WWWWGWGWW", "WWWWWGWWW"}

    Returns: 57

  94. {"G", "G"}

    Returns: 0

  95. {"RGWWWGRR", "WRWRGRWR", "WRWGWWRW", "WRGWRWRW", "RRGRRWRG", "GWWWRGRR"}

    Returns: 15

  96. {"RGGGGR", "GRWGGR", "RWGRWR", "RRGGRG", "WGGGRG", "GGGGWR", "GRRRWW", "GGGGWR"}

    Returns: 5

  97. {"WWWGWWWWW", "WWWGWGWWR"}

    Returns: 8

  98. {"WWWGWW", "WGWWWW", "WWGWGW", "WGGWGW", "GWGWWG", "WWGGWG", "GWWWWW", "WWWWGW", "RWWGWW", "RWWRRW"}

    Returns: 35

  99. {"GGRRGGGG", "RGWGGRGR", "GGRGGRGG", "GRGGGGWW", "RGGRGGRR", "RRRRRWRG", "GRRRRRGG", "RRRGGRWG", "GRGRRGRR"}

    Returns: 2

  100. {"GW", "WW", "GG", "WW", "WW", "WR", "WW"}

    Returns: 5

  101. {"RWRRRR", "RWRRWW", "RRRWWG"}

    Returns: 2

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: