BichromeBoard | Topcoder Archive

Problem Statement

We have a rectangular board divided into a grid of unit squares. We are going to color each square either white or black.

You are given the String[] board. Each character in board represents one unit square. If board[i][j] is 'B', the corresponding square must be black. If board[i][j] is 'W', the corresponding square must be white. Finally, if board[i][j] is '?', you get to choose the color for this square: either white or black.

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.

Definition

Class:: BichromeBoard
Method:: ableToDraw
Parameters:: String[]
Returns:: String
Method signature:: String ableToDraw(String[] board)
(be sure your method is public)

Constraints

board will contain between 1 and 50 elements, inclusive.
Each element in board will contain between 1 and 50 characters, inclusive.
Each element in board will contain the same number of characters.
Each character in board will be one of 'W', 'B', '?'.

Examples

{"W?W",
 "??B",
 "???"}

Returns: "Possible"

The solution is: WBW BWB WBW

```
{"W??W"}
```
```
Returns: "Impossible"
```
The four possible colorings of this board are WWWW, WWBW, WBWW, and WBBW. In each of them there is at least one pair of adjacent squares that share the same color. Thus, there is no way to get a pattern with the desired property.
```
{"??"}
```
```
Returns: "Possible"
```
There are 2 ways: WB and BW

{"W???",
 "??B?",
 "W???",
 "???W"}

Returns: "Possible"

{"W???",
 "??B?",
 "W???",
 "?B?W"}

Returns: "Impossible"

```
{"B"}
```
```
Returns: "Possible"
```

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.