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.
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
{"??", "??"}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.{"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.{"WW", "WW"}Returns: 0
This board is already colored and the coloring is not rectangle-avoiding.{"??B??", "W???W", "??B??"}Returns: 12
Back to all problems