Statistics

Problem Statement for "RectangleAvoidingColoringEasy"

Problem Statement

There is an N x M board divided into 1 x 1 cells. The rows of the board are numbered from 0 to N-1, and the columns are numbered from 0 to M-1. The cell located in row r and column c has coordinates (r, c).

In a coloring of the board, each cell on the board is colored white or black. A coloring is called rectangle-avoiding if it is impossible to choose 4 distinct cells of the same color so that their centers form a rectangle whose sides are parallel to the sides of the board. In other words, a coloring is rectangle-avoiding if, for each a, b, c, and d with 0 <= a < b < N, 0 <= c < d < M, there is at least one white cell and at least one black cell among the cells (a, c), (a, d), (b, c) and (b, d).

You are given a String[] board representing a board. The j-th character of the i-th element of board represents cell (i, j), and it can be 'W', 'B' or '?'. Here, 'W' indicates a white cell, 'B' indicates a black cell and '?' indicates an uncolored cell. For each uncolored cell, you may choose to color it either white or black. Return the number of different rectangle-avoiding colorings that can be achieved. If it is impossible to achieve a rectangle-avoiding coloring, return 0.

Definition

Class:
RectangleAvoidingColoringEasy
Method:
count
Parameters:
String[]
Returns:
int
Method signature:
int count(String[] board)
(be sure your method is public)

Notes

  • Two colorings are different if there is a cell on the board that is colored white in one coloring and black in the other coloring.
  • The answer will always fit into a 32-bit signed integer data type.

Constraints

  • board will contain between 1 and 10 elements, inclusive.
  • Each element of board will contain between 1 and 10 characters, inclusive.
  • All elements of board will contain the same number of characters.
  • Each character in each element of board will be 'W', 'B' or '?'.

Examples

  1. {"??", "??"}

    Returns: 14

    Since each cell can be black or white, there are 2^4 = 16 ways to color this board. Of them, only 2 monochromatic colorings are not rectangle-avoiding, so the answer is 16 - 2 = 14.

  2. {"B?", "?B"}

    Returns: 3

    It is the same board as in previous example, but colors for some cells are already predefined. There are 4 ways to color the remaining cells and in one of them the board becomes completely black. Therefore the answer is 4 - 1 = 3.

  3. {"WW", "WW"}

    Returns: 0

    This board is already colored and the coloring is not rectangle-avoiding.

  4. {"??B??", "W???W", "??B??"}

    Returns: 12

  5. {"?"}

    Returns: 2

  6. {"B"}

    Returns: 1

  7. {"W"}

    Returns: 1

  8. {"??"}

    Returns: 4

  9. {"BB"}

    Returns: 1

  10. {"BB"}

    Returns: 1

  11. {"???"}

    Returns: 8

  12. {"W?BWBWBBB"}

    Returns: 2

  13. {"WW?W?B?"}

    Returns: 8

  14. {"??????????"}

    Returns: 1024

  15. {"BWBWBWWBWW"}

    Returns: 1

  16. {"WWB?BW?WB?"}

    Returns: 8

  17. {"?","?"}

    Returns: 4

  18. {"B","B"}

    Returns: 1

  19. {"W","?"}

    Returns: 2

  20. {"?","?","?"}

    Returns: 8

  21. {"B","B","W","W"}

    Returns: 1

  22. {"B","B","B"}

    Returns: 1

  23. {"???????","???????","???????","???????","???????","???????","???????","???????","???????","???????"}

    Returns: 0

  24. {"?","?","?","?","?","?","?","?","?","?"}

    Returns: 1024

  25. {"??","??"}

    Returns: 14

  26. {"?B","?W"}

    Returns: 4

  27. {"??","W?"}

    Returns: 7

  28. {"???","???"}

    Returns: 44

  29. {"BBBBWBB","BWBWBBW"}

    Returns: 0

  30. {"WW?BWWWBW","B?BB?B?WB"}

    Returns: 4

  31. {"??","??","??"}

    Returns: 44

  32. {"??","BB","BW","WB","WB"}

    Returns: 3

  33. {"W?","?W","?W","?W","B?","??","?W","??","??"}

    Returns: 204

  34. {"??????????","??????????"}

    Returns: 34304

  35. {"W??BWB?WW?","???B???WB?"}

    Returns: 16

  36. {"WBWWBBBWBB","B?BBBWWB?W"}

    Returns: 1

  37. {"??","??","??","??","??","??","??","??","??","??"}

    Returns: 34304

  38. {"?W","WB","BB","?B","?W","BW","WW","WB","BW","BB"}

    Returns: 0

  39. {"B?","B?","BW","WB","??","BB","BW","??","W?","BW"}

    Returns: 12

  40. {"???","???","???"}

    Returns: 156

  41. {"WWW","W??","???"}

    Returns: 2

  42. {"?WB","W?W","?W?"}

    Returns: 4

  43. {"????","????","????"}

    Returns: 408

  44. {"B?BW","?BB?","B??B"}

    Returns: 3

  45. {"?W??","??W?","?WB?"}

    Returns: 28

  46. {"???","???","???","???"}

    Returns: 408

  47. {"WB?","?W?","?WW","BWB"}

    Returns: 2

  48. {"???","?B?","?BB","??B"}

    Returns: 14

  49. {"?????","?????","?????"}

    Returns: 720

  50. {"WW?BB","WWWW?","BBWWW"}

    Returns: 0

  51. {"B?WB?","??BBB","??W?B"}

    Returns: 4

  52. {"???","???","???","???","???"}

    Returns: 720

  53. {"??B","BBB","B?W","?WB","W?B"}

    Returns: 0

  54. {"B??","?BW","W??","WW?","WB?"}

    Returns: 4

  55. {"???????","???????","???????"}

    Returns: 0

  56. {"?B?WW??","BW?B??W","????B?B"}

    Returns: 0

  57. {"???","???","???","???","???","???","???","???","???"}

    Returns: 0

  58. {"WWB","BBB","BWB","WWB","BBB","WBB"}

    Returns: 0

  59. {"??????????","??????????","??????????"}

    Returns: 0

  60. {"BBWBB?BBWB","BWWBWBWW?W","WWWWBBWWB?"}

    Returns: 0

  61. {"???","???","???","???","???","???","???","???","???","???"}

    Returns: 0

  62. {"WBW","WWW","W?W","WW?","WWW","WWW","W?W","WWW","BWW","WBW"}

    Returns: 0

  63. {"????","????","????","????"}

    Returns: 840

  64. {"W?W?","W?WW","W?W?","BBWW"}

    Returns: 0

  65. {"B?BW","W???","WBWW","BW??"}

    Returns: 3

  66. {"?????","?????","?????","?????"}

    Returns: 720

  67. {"WB?WB","?WBBB","?W?B?","BBB?W"}

    Returns: 1

  68. {"B????","B???W","???B?","?????"}

    Returns: 42

  69. {"????","????","????","????","????"}

    Returns: 720

  70. {"?BBB","B?BB","BBBB","BWBB","B?BB"}

    Returns: 0

  71. {"W???","?B?W","?B??","???W","?W??"}

    Returns: 14

  72. {"????????","????????","????????","????????"}

    Returns: 0

  73. {"WWBWW?BB","WB???WBB","BW??BBBW","BBWWWWBB"}

    Returns: 0

  74. {"????","????","????","????","????","????","????","????","????"}

    Returns: 0

  75. {"WBBB","BBBB","W?BB","WBBB","WW?B","B?WB"}

    Returns: 0

  76. {"??????????","??????????","??????????","??????????"}

    Returns: 0

  77. {"BW???W?BBB","?WBW????B?","W??????BB?","W?WBB?B?BW"}

    Returns: 0

  78. {"????","????","????","????","????","????","????","????","????","????"}

    Returns: 0

  79. {"BB??","?W?B","BB??","?BB?","?B??","BWBB","WW??","WBB?","??WB","?W??"}

    Returns: 0

  80. {"????????","????????","????????","????????","????????","????????","????????"}

    Returns: 0

  81. {"WBWWWBWWB","WWWWWBW?W","B?WW?W?W?","WWB?WWWW?","WWBWWWWBW","BWWW?WWWB","B??WBWW?W","BBB??WWWB","WWWWWBWWB"}

    Returns: 0

  82. {"????????","????????","????????","????????","????????","????????","????????","????????"}

    Returns: 0

  83. {"??B?B????","??BBB?W??","????B??B?","?BBBWBW?B","WB?BB???B","BW?BB??WW","?W??B?WW?"}

    Returns: 0

  84. {"??????????","??????????","??????????","??????????","??????????","??????????","??????????","??????????","??????????"}

    Returns: 0

  85. {"WBBWWBBBWW","?BB?BBBWWB","BBBBBBBWWB","WWBBBBBWWW","?BWW?BWBWW","WWWB?WWB?B","BBBBB?BWBB"}

    Returns: 0

  86. {"???????","???????","???????","???????","???????","???????","???????","???????","???????","???????"}

    Returns: 0

  87. {"WWWWWW","WWWWWW","WWWWWW","WWWWWW","WWWWWW","WWWWWW","?WWWWW","WWWWWW","WWWWWW","WWWWWW"}

    Returns: 0

  88. {"??????????","??????????","??????????","??????????","??????????","??????????","??????????","??????????","??????????","??????????"}

    Returns: 0

  89. {"?BBBWWWBWW","W??BB??WWW","?W?BWB?WBB","WW?WW?BWWW","WB?WBBBBBW","?WBW?BWWWW","WWWBWBBBBB","WWWBWB?WWB","WBBBWWBWB?","BWWWBWBWWW"}

    Returns: 0

  90. {"???B??????"}

    Returns: 512

  91. {"???????B??"}

    Returns: 512

  92. {"?B????????"}

    Returns: 512

  93. {"??????????","W?????????"}

    Returns: 17152

  94. {"?????W????","?B????????"}

    Returns: 8704

  95. {"W?????????","W?????????"}

    Returns: 2816

  96. {"????B","?????","??W??"}

    Returns: 168

  97. {"?B???","?B???","?????"}

    Returns: 120

  98. {"W????","?????","????W"}

    Returns: 192

  99. {"?????","??B??","????W","?????"}

    Returns: 168

  100. {"W????","?????","W????","?????"}

    Returns: 120

  101. {"???B?","?????","????B","?????"}

    Returns: 192

  102. {"B","?","?","?","?","?","?","?","?","?"}

    Returns: 512

  103. {"?","?","?","?","?","W","?","?","W","?"}

    Returns: 256

  104. {"W","?","?","?","?","?","?","W","?","?"}

    Returns: 256

  105. {"??","??","?B","??","??","??","??","??","??","??"}

    Returns: 17152

  106. {"??","??","??","B?","??","??","??","??","B?","??"}

    Returns: 8448

  107. {"??","B?","??","??","??","??","W?","??","??","??"}

    Returns: 8704

  108. {"???","???","???","W??","?W?"}

    Returns: 192

  109. {"???","???","?W?","???","???"}

    Returns: 360

  110. {"??W","???","???","???","???"}

    Returns: 360

  111. {"????","????","????","?W??","????"}

    Returns: 360

  112. {"???B","????","???B","????","????"}

    Returns: 144

  113. {"????","W???","????","B???","????"}

    Returns: 216

  114. {"??????????","??????????","???????B??","??????????","??????????","??????????","??????????","??????????","??????????","??????????"}

    Returns: 0

  115. {"??????B???","??????????","?????????W","??????????","??????????","??????????","??????????","??????????","??????????","??????????"}

    Returns: 0

  116. {"??????????","??????????","??????????","??????????","??????????","??????????","??????????","?????W????","??????????","????????W?"}

    Returns: 0

  117. {"??????","???B??","???W??","??????","??????","??????","??????"}

    Returns: 0

  118. {"?W?????"}

    Returns: 64

  119. {"???","???","???","???","???","???","??B","???","???"}

    Returns: 0

  120. {"????????B?"}

    Returns: 512

  121. {"???????W","????????","????????","????????","????????","W???????"}

    Returns: 0

  122. {"W","?","?","?","?","W"}

    Returns: 16

  123. {"?????","?????","W??B?","?????"}

    Returns: 216

  124. {"???","???","???","???","???","???","???","???","???","?W?"}

    Returns: 0

  125. {"??????","?W????","??????"}

    Returns: 360

  126. {"?B?????W"}

    Returns: 64

  127. {"?B????","??????","??????","??????","??????","??????"}

    Returns: 0

  128. {"??????","??????","W?????"}

    Returns: 360

  129. {"???????","???????","???????","???????","???????","????B??","???????"}

    Returns: 0

  130. {"??????","??????","??????"}

    Returns: 720

  131. {"WBW??B","??????","?WW???"}

    Returns: 16

  132. {"????WW","WW??W?","???W??"}

    Returns: 6

  133. {"??????","??????","??????","??????"}

    Returns: 720

  134. {"?WB???","?B?W??","??BWBW","?WW???"}

    Returns: 2

  135. {"????BB","??????","??????","?B????"}

    Returns: 84

  136. {"???","???","???","???","???","???"}

    Returns: 720

  137. {"BW?","?W?","?BB","W??","?WW","???"}

    Returns: 1

  138. {"?W?","??B","B?W","???","?W?","?W?"}

    Returns: 6

  139. {"????","????","????","????","????","????"}

    Returns: 720

  140. {"?B?B","?WBB","??BW","?WB?","?W?W","B?WB"}

    Returns: 0

  141. {"W???","?B??","W??W","??W?","B???","B??B"}

    Returns: 2

  142. {"??????","??????","????B?"}

    Returns: 360

  143. {"??????","W?????","??????"}

    Returns: 360

  144. {"????W?","????B?","??????"}

    Returns: 240

  145. {"?BW???","??????","??????","??????"}

    Returns: 216

  146. {"??B???","?????B","??????","??????"}

    Returns: 192

  147. {"??????","??????","???W?W","??????"}

    Returns: 144

  148. {"???","B??","???","???","???","???"}

    Returns: 360

  149. {"???","??W","???","???","???","???"}

    Returns: 360

  150. {"???","???","??B","???","???","???"}

    Returns: 360

  151. {"????","B???","????","????","????","????"}

    Returns: 360

  152. {"????","????","????","????","????","W???"}

    Returns: 360

  153. {"B???","????","????","????","?B??","????"}

    Returns: 192

  154. {"?????","?????","?????","?????","?????"}

    Returns: 0

  155. {"W???W","WB?WB","??B??","WWW??","W??WW"}

    Returns: 0

  156. {"??????","??????","??????","??????","??????"}

    Returns: 0

  157. {"W?WWBBW?B","BW?W?BWB?","BBBBBBWBW","BBWWBWBWW","WWBWWBWBW"}

    Returns: 0

  158. {"?????","?????","?????","?????","?????","?????"}

    Returns: 0

  159. {"BWWBB","BWBBB","WBWWW","BWBWW","WBWB?","BWBWB","BBBBB"}

    Returns: 0

  160. {"??????????","??????????","??????????","??????????","??????????"}

    Returns: 0

  161. {"BBBBB??WBB","BB??BBBBBW","WWBBBBBWBB","BW?WB?BB?W","B?BWBW?BBB"}

    Returns: 0

  162. {"?????","?????","?????","?????","?????","?????","?????","?????","?????","?????"}

    Returns: 0

  163. {"??W?W","W?BWW","?WW?W","???W?","???WW","???W?","W?WWW","WW?WW","WW??W","???BW"}

    Returns: 0

  164. {"B???????W?", "??????????", "??????????", "??????????", "??????????", "??????????", "??????????", "?????B????", "??????W???", "??????????" }

    Returns: 0

  165. {"WB??B?????", "WB??B?????", "WB??B?????", "WB??B???BB", "WB??B?????", "WB??B?WW??", "WB??B?????", "WB??B??B??", "WB??B?????", "WB??B?W???" }

    Returns: 0

  166. {"??????????", "??????????", "??????????", "??????????", "??????????", "??????????", "??????????", "??????????", "??????????", "??????????" }

    Returns: 0

  167. {"??B??", "W???W", "??B??" }

    Returns: 12

  168. {"W???B", "?W??B", "W????", "??B?W" }

    Returns: 8

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: