Statistics

Problem Statement for "ElephantDrinkingEasy"

Problem Statement

There is an n times n field. Some of the cells of the field contain water. You are given a map of the field encoded as a String[] field. There are n elements in field and each of them has n characters. The character field[i][j] is 'Y' if there is water in the cell (i,j). Otherwise, the corresponding character is 'N'.


There are 4n elephants around the field: one per each cell boundary, as shown in the pictures below. The elephants can use their trunks to drink water. Each elephant can only extend its trunk straight into the field. So, for example, the elephants that are on the left side of the field can only extend their noses towards the right. The trunks are long enough to reach the opposite end of the field.




There are two additional restrictions: The trunks of elephants are not allowed to intersect. For each cell with water, there can be at most one elephant drinking from that cell.


For example, figure (a) below shows a valid configuration. Cells with water are blue, elephants are green, and their trunks are red. In the figure there are four elephants that drink. Figures (b) and (c) show invalid configurations. In both of them the trunks intersect.


Your task is to return the maximal number of elephants who can drink at the same time.

Definition

Class:
ElephantDrinkingEasy
Method:
maxElephants
Parameters:
String[]
Returns:
int
Method signature:
int maxElephants(String[] map)
(be sure your method is public)

Constraints

  • n will be between 2 and 5, inclusive.
  • field will contain exactly n elements, inclusive.
  • Each element in field will contain exactly n characters, inclusive.
  • Each character in field will be 'Y' or 'N'.

Examples

  1. {"NNNNN", "NNYYN", "NYNNN", "NNYNN", "NNNNN"}

    Returns: 4

    This is the field shown in the figure in the problem statement. As shown in figure (a), four elephants can drink at the same time. And as we only have four cells with water, this is clearly optimal.

  2. {"YYY", "YYY", "YYY"}

    Returns: 8

    It is possible for the elephants to drink from 8 cells at the same time. For example, a suitable set of 8 elephants can drink from all cells except for the one in the center. It is not possible for the elephants to drink from all 9 cells at the same time.

  3. {"YNYN", "NNYY", "YYNN", "YYYY"}

    Returns: 10

  4. {"YNYN", "YNYY", "YYNN", "YYYY"}

    Returns: 10

  5. {"YYNYN", "NYNNY", "YNYNN", "YYNYY", "YYNNN"}

    Returns: 12

  6. {"YYNYN", "NYNYY", "YNYYN", "YYNYY", "YYNNN"}

    Returns: 13

  7. {"NN", "NN"}

    Returns: 0

    There can be no water at all.

  8. {"YYYY","YYYY","YYYY","YYYY"}

    Returns: 12

  9. {"YYYN","YYNY","NNNN","YNYY"}

    Returns: 9

  10. {"NNYY","NNNN","NNNY","NNNN"}

    Returns: 3

  11. {"YYY","NNN","YNY"}

    Returns: 5

  12. {"YYYYY","YNNNN","YYYYY","YNYYY","YNYNY"}

    Returns: 15

  13. {"YYYY","YNYY","YYYY","YNNY"}

    Returns: 12

  14. {"NNNNN","YNNYN","NNNNN","NNNNY","NNNNN"}

    Returns: 3

  15. {"NNNNN","NNNNN","NNNNN","NNNNN","NNNNN"}

    Returns: 0

  16. {"NNNNN","NNNNN","NNNNN","NYNNN","NNNNY"}

    Returns: 2

  17. {"YYY","YNY","YNY"}

    Returns: 7

  18. {"NNN","NYN","NNN"}

    Returns: 1

  19. {"YNN","YNY","YYY"}

    Returns: 6

  20. {"NNNN","NNNN","NNNN","NNNN"}

    Returns: 0

  21. {"YYYYY","YYYYY","YNNNY","YYYYY","YNYYY"}

    Returns: 16

  22. {"YY","YN"}

    Returns: 3

  23. {"YYY","YYY","YYY"}

    Returns: 8

  24. {"NNNYN","NNNNN","NNNNN","NNNNY","YYYNN"}

    Returns: 5

  25. {"NNYY","NYNN","NNYN","NYYY"}

    Returns: 7

  26. {"YNY","YYY","YNN"}

    Returns: 6

  27. {"YYYY","NYYY","YYYY","YYYY"}

    Returns: 12

  28. {"YYY","YNN","YYN"}

    Returns: 6

  29. {"YY","YY"}

    Returns: 4

  30. {"YNYY","NYYY","YNYY","YYYY"}

    Returns: 11

  31. {"NNN","YNN","NNN"}

    Returns: 1

  32. {"NYNYN","NNNNN","NNNNN","NNNYN","NNNNN"}

    Returns: 3

  33. {"YYYYN","YYNYY","YYYNY","YYNYY","YYYYY"}

    Returns: 15

  34. {"NNY","YNN","NNN"}

    Returns: 2

  35. {"NNNN","NNNN","NNNN","NNNY"}

    Returns: 1

  36. {"NNN","NNN","NNN"}

    Returns: 0

  37. {"NNYY","YYYN","NNNN","NYNY"}

    Returns: 7

  38. {"NN","NN"}

    Returns: 0

  39. {"YY","YY"}

    Returns: 4

  40. {"NNN","NNN","NNY"}

    Returns: 1

  41. {"NN","NN"}

    Returns: 0

  42. {"YYYYN","YNYYY","YYYYY","YYNYN","YNYNY"}

    Returns: 14

  43. {"YNYYY","YYNNY","YYYYY","NYYNY","YYNYN"}

    Returns: 15

  44. {"NNYN","YYNY","YYNY","YNNN"}

    Returns: 8

  45. {"YYYY","YYYY","YYYY","YYYY"}

    Returns: 12

  46. {"YNNN","NNNN","NNYY","NYYN"}

    Returns: 5

  47. {"NNNN","NNNN","NNYY","NNNY"}

    Returns: 3

  48. {"YYYY","YYYY","YYYY","NYYY"}

    Returns: 11

  49. {"YYYY","YNYN","YNYN","NYYN"}

    Returns: 10

  50. {"NNNN","NNNY","NNNN","NYNN"}

    Returns: 2

  51. {"YYY","YNY","NNN"}

    Returns: 5

  52. {"YNNY","YYYN","YYNY","YYNY"}

    Returns: 10

  53. {"NY","NN"}

    Returns: 1

  54. {"YYNYN","NNNNN","YYYYY","YNYYN","YNYNY"}

    Returns: 12

  55. {"YNY","YYY","YYY"}

    Returns: 8

  56. {"YY","YY"}

    Returns: 4

  57. {"NNNNY","NYNNN","NNNNN","NYNYN","NNNYY"}

    Returns: 6

  58. {"YNN","YNN","NNN"}

    Returns: 2

  59. {"YNNYN","YYYYY","NNYYY","YYNYN","YNYYY"}

    Returns: 15

  60. {"NNY","NYN","NNN"}

    Returns: 2

  61. {"NYNN","YYYN","YNYY","YYYN"}

    Returns: 8

  62. {"NNNN","YNYN","YNNN","YYYN"}

    Returns: 6

  63. {"NYYYN","YNYNY","YYNNN","NYNYY","YNNNN"}

    Returns: 11

  64. {"YNYYY","NYNNY","NYYYY","NYNNN","YYNNY"}

    Returns: 14

  65. {"YNNYY","YYNNN","YNYNN","YNNYN","NNNNN"}

    Returns: 9

  66. {"YYNY","YNNN","YYYY","NYYN"}

    Returns: 9

  67. {"YNYNN","NNNYN","NNYNN","NNYNY","YNNYN"}

    Returns: 8

  68. {"NN","NN"}

    Returns: 0

  69. {"NNNY","NNNY","YNNN","NNNN"}

    Returns: 3

  70. {"NNNNN","NNNNN","YNNNN","NNNNN","NNNNY"}

    Returns: 2

  71. {"YYNN","NNNN","NYYN","YYNY"}

    Returns: 7

  72. {"YY","NY"}

    Returns: 3

  73. {"NYNN","YNNN","NNYY","NNYN"}

    Returns: 5

  74. {"YY","YY"}

    Returns: 4

  75. {"YYYY","YYYN","NYYY","YYYN"}

    Returns: 11

  76. {"YYY","YNY","YYN"}

    Returns: 7

  77. {"NNNNN","NNNNN","NNNNN","NNNNN","NNNNY"}

    Returns: 1

  78. {"NNN","NNN","NNN"}

    Returns: 0

  79. {"YYY","NYY","YNN"}

    Returns: 6

  80. {"NNNNN","NYYNN","NNNNN","NNNNN","NNNNN"}

    Returns: 2

  81. {"NY","YY"}

    Returns: 3

  82. {"YNY","YYN","YYN"}

    Returns: 6

  83. {"NN","NN"}

    Returns: 0

  84. {"NN","YN"}

    Returns: 1

  85. {"YNYY","YNYN","YNNN","NNNY"}

    Returns: 7

  86. {"YYYYY","YYYNY","YYNYN","YYYYN","NYYYN"}

    Returns: 14

  87. {"NNNNY","NNNNN","NYNNN","YYNNY","NNYNY"}

    Returns: 7

  88. {"YY","YY"}

    Returns: 4

  89. {"NNNN","NYNN","NNNY","NNNY"}

    Returns: 3

  90. {"YYNN","YNYN","YYYY","YYNN"}

    Returns: 9

  91. {"YNN","YYY","NYN"}

    Returns: 5

  92. {"YYY","NNN","NYY"}

    Returns: 5

  93. {"NNNN","NNNN","NNNN","NYNN"}

    Returns: 1

  94. {"YN","NN"}

    Returns: 1

  95. {"NNNNN","NNYNN","NNNYN","NNNNN","NNNNN"}

    Returns: 2

  96. {"YNN","NYN","YNN"}

    Returns: 3

  97. {"YNNYN","NNNNY","YNNNN","NYYNY","YYNYY"}

    Returns: 11

  98. {"NYNY","YYYN","YYNY","YYYY"}

    Returns: 10

  99. {"YYYYY","YYNYN","YNNNY","YYYYN","YYYYN"}

    Returns: 15

  100. {"YNNNN","NNYYY","YYYYY","NNNNY","YYYYY"}

    Returns: 13

  101. {"NNNNN","NYNNN","NNNNN","NNNNN","NNYYN"}

    Returns: 3

  102. {"NNNNN","NNNNN","NNNNN","NNNNN","NNNNN"}

    Returns: 0

  103. {"YNYY","YNYY","YYYY","YNYY"}

    Returns: 11

  104. {"YYNYY","YYYNY","YNYNY","NNYNY","YNNYY"}

    Returns: 15

  105. {"NN","NN"}

    Returns: 0

  106. {"NNN","NYN","NYN"}

    Returns: 2

  107. {"NNN","NNN","NNN"}

    Returns: 0

  108. {"YYYYY","YYYYY","YYYYY","YYYYY","YYYYY"}

    Returns: 16

  109. {"YNYN", "YNYY", "YYNN", "YYYY" }

    Returns: 10

  110. {"YNYN", "NNYY", "YYNN", "YYYY" }

    Returns: 10

  111. {"NYYN", "YNYY", "YYNN", "NYNN" }

    Returns: 7

  112. {"YYYY", "YYYY", "YYYY", "YYYY" }

    Returns: 12

  113. {"YYNNN", "YYNNN", "YYYYY", "YYYYY", "NNNNN" }

    Returns: 12

  114. {"YYNYN", "NYNYY", "YNYYN", "YYNYY", "YYNNN" }

    Returns: 13

  115. {"NNYYN", "NNYYN", "YYNNN", "NYNNN", "NNNNN" }

    Returns: 7

  116. {"NNNYN", "YNNNN", "NNNYY", "YYYNY", "YYYYY" }

    Returns: 12

  117. {"YYYY", "YYYY", "NNYY", "YNYY" }

    Returns: 11

  118. {"NNYY", "NNYY", "YYYN", "NYNN" }

    Returns: 7

  119. {"YNNNY", "NYYNY", "YYYYY", "NNNNN", "NNNNN" }

    Returns: 10

  120. {"NYYNN", "NYYNN", "YNNYY", "YNNYY", "NYYNN" }

    Returns: 11

  121. {"YNYNN", "NYYNY", "NYYYN", "NYYYN", "YNNNN" }

    Returns: 10

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: