forked from keshavnandan/Topcoder
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathBichromeBoard.html
31 lines (31 loc) · 4.82 KB
/
BichromeBoard.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
<html><body bgcolor="#000000" text="#ffffff"><table><tr><td colspan="2"><h3>Problem Statement</h3></td></tr><tr><td>    </td><td>We have a rectangular board divided into a grid of unit squares.
We are going to color each square either white or black.
<br></br>
<br></br>
You are given the vector <string> <b>board</b>.
Each character in <b>board</b> represents one unit square.
If <b>board</b>[i][j] is 'B', the corresponding square must be black.
If <b>board</b>[i][j] is 'W', the corresponding square must be white.
Finally, if <b>board</b>[i][j] is '?', you get to choose the color for this square: either white or black.
<br></br>
<br></br>
Two squares are adjacent if they share a common side.
We want to color the board in such a way that no two adjacent squares share the same color.
Return "Possible" (quotes for clarity) if it can be done, or "Impossible" otherwise.</td></tr><tr><td colspan="2"><h3>Definition</h3></td></tr><tr><td>    </td><td><table><tr><td>Class:</td><td>BichromeBoard</td></tr><tr><td>Method:</td><td>ableToDraw</td></tr><tr><td>Parameters:</td><td>vector <string></td></tr><tr><td>Returns:</td><td>string</td></tr><tr><td>Method signature:</td><td>string ableToDraw(vector <string> board)</td></tr><tr><td colspan="2">(be sure your method is public)</td></tr></table></td></tr><tr><td colspan="2"><h3>Limits</h3></td></tr><tr><td>    </td><td><table><tr><td>Time limit (s):</td><td>2.000</td></tr><tr><td>Memory limit (MB):</td><td>256</td></tr><tr><td>Stack limit (MB):</td><td>256</td></tr></table></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 in <b>board</b> will contain between 1 and 50 characters, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td>Each element in <b>board</b> will contain the same number of characters.</td></tr><tr><td align="center" valign="top">-</td><td>Each character in <b>board</b> will be one of 'W', 'B', '?'.</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>{"W?W",
"??B",
"???"}</pre></td></tr></table></td></tr><tr><td><pre>Returns: "Possible"</pre></td></tr><tr><td><table><tr><td colspan="2">The solution is:
<pre>
WBW
BWB
WBW
</pre>
</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>{"W??W"}</pre></td></tr></table></td></tr><tr><td><pre>Returns: "Impossible"</pre></td></tr><tr><td><table><tr><td colspan="2">The four possible colorings of this board are WWWW, WWBW, WBWW, and WBBW.<br></br>
In each of them there is at least one pair of adjacent squares that share the same color.<br></br>
Thus, there is no way to get a pattern with the desired property.<br></br></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>{"??"}</pre></td></tr></table></td></tr><tr><td><pre>Returns: "Possible"</pre></td></tr><tr><td><table><tr><td colspan="2">There are 2 ways:
WB and BW</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>{"W???",
"??B?",
"W???",
"???W"}</pre></td></tr></table></td></tr><tr><td><pre>Returns: "Possible"</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???",
"??B?",
"W???",
"?B?W"}</pre></td></tr></table></td></tr><tr><td><pre>Returns: "Impossible"</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">5)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{"B"}</pre></td></tr></table></td></tr><tr><td><pre>Returns: "Possible"</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>