forked from daiwb/Algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathRectangleAvoidingColoring.html
More file actions
14 lines (14 loc) · 5.26 KB
/
RectangleAvoidingColoring.html
File metadata and controls
14 lines (14 loc) · 5.26 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
<html><body bgcolor="#000000" text="#ffffff"><table><tr><td colspan="2"><h3>Problem Statement</h3></td></tr><tr><td>    </td><td>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).
<br></br><br></br>
In a coloring of the board, each cell on the board is colored white or black. A coloring is called <i>rectangle-avoiding</i> 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).
<br></br><br></br>
You are given a vector <string> <b>board</b> representing a board. The j-th character of the i-th element of <b>board</b> 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.</td></tr><tr><td colspan="2"><h3>Definition</h3></td></tr><tr><td>    </td><td><table><tr><td>Class:</td><td>RectangleAvoidingColoring</td></tr><tr><td>Method:</td><td>count</td></tr><tr><td>Parameters:</td><td>vector <string></td></tr><tr><td>Returns:</td><td>long long</td></tr><tr><td>Method signature:</td><td>long long count(vector <string> board)</td></tr><tr><td colspan="2">(be sure your method is public)</td></tr></table></td></tr><tr><td>    </td></tr><tr><td></td></tr><tr><td colspan="2"><h3>Notes</h3></td></tr><tr><td align="center" valign="top">-</td><td>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.</td></tr><tr><td align="center" valign="top">-</td><td>The answer will always fit into a 64-bit signed integer data type.</td></tr><tr><td colspan="2"><h3>Constraints</h3></td></tr><tr><td align="center" valign="top">-</td><td><b>board</b> will contain between 1 and 50 elements, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td>Each element of <b>board</b> will contain between 1 and 50 characters, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td>All elements of <b>board</b> will contain the same number of characters.</td></tr><tr><td align="center" valign="top">-</td><td>Each character in each element of <b>board</b> will be 'W', 'B' or '?'.</td></tr><tr><td colspan="2"><h3>Examples</h3></td></tr><tr><td align="center" nowrap="true">0)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{"??",
"??"}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 14</pre></td></tr><tr><td><table><tr><td colspan="2">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.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">1)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{"B?",
"?B"}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 3</pre></td></tr><tr><td><table><tr><td colspan="2">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.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">2)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{"WW",
"WW"}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 0</pre></td></tr><tr><td><table><tr><td colspan="2">This board is already colored and the coloring is not rectangle-avoiding.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">3)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{"??B??",
"W???W",
"??B??"}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 12</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">4)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{"??",
"W?",
"W?",
"?W",
"W?"}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 16</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr></table><p>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)2003, TopCoder, Inc. All rights reserved. </p></body></html>