Othello Endgame Outcome Counting

This problem involves analyzing an endgame position in the game of Othello (also known as Reversi). The board is an n × n grid where each cell may contain a black piece (B), a white piece (W), or be empty (denoted by .). In the given situation, there are at most 10 empty cells. The game is played by two players who take turns placing their piece on a legal cell. White moves first.

A move is legal if and only if, by placing a piece of the current player's color on an empty square, the player sandwiches one or more straight (horizontal, vertical, or diagonal) lines of contiguous opponent pieces between the new piece and another piece of the current player's color. Formally, for a move at cell (i, j) with player p and opponent q, there must exist at least one direction among the 8 possible directions such that:

\( \begin{array}{l} \text{The immediate cell in that direction is } q, \\ \text{and continuing in that direction, after one or more } q's, \\ a cell containing } p \text{ is encountered (with no empty cell in between).} \end{array} \)

Whenever a legal move is made, all the opponent pieces that are sandwiched along any qualifying direction are flipped to the current player's color.

If the current player has no legal moves, the turn passes to the opponent. The game ends when neither player can make a legal move. At that point, if black has more pieces on the board than white, the outcome is considered a black win; if white has more pieces than black, it is a white win; otherwise, it is a draw.

Your task is to count, over all possible sequences of moves (assuming both players follow the rules described above), how many final outcomes result in a black win, a white win, and a draw. Note that the given board position does not necessarily need to be reachable from a standard initial configuration.

inputFormat

The first line contains an integer n (the board size). The following n lines each contain a string of length n, representing a row of the board. Each character is either B (black), W (white), or . (empty). It is guaranteed that there are at most 10 empty cells.

outputFormat

Output three integers separated by a space: the number of final outcomes (i.e. complete game sequences) where black wins, white wins, and the game ends in a draw, respectively.

sample

2
BW
WB

0 0 1