Chessboard Four-in-Line Puzzle

On a 4×4 board, there are exactly 14 pieces – 7 white pieces and 7 black pieces – and 2 empty cells. A move is defined as moving any piece (regardless of color) from its current cell to an adjacent empty cell in one of the four cardinal directions (up, down, left, right). The moves are made alternately by the two sides, and either side may start. At any moment, if all 4 cells in any row, any column, or either of the two main diagonals (i.e. the main diagonal or the anti‐diagonal) are occupied by pieces of the same color (and none of them is empty), the board is said to be in a target state.

Given an initial board configuration (which obeys the above pieces count restrictions), determine the minimum number of moves needed to reach a target state. If a target state cannot be reached in at most 10 moves, output −1.

Note: The board is represented by 4 lines with 4 characters each. Each character is either 'W' (white), 'B' (black), or '.' (empty). It is guaranteed that there are exactly 14 pieces and 2 empty cells, and that there are exactly 7 white and 7 black pieces.

Winning Condition (in LaTeX):
A board state is winning if any of the following holds: \[ \begin{aligned} &\text{For some } i:\; board_{i,0} = board_{i,1} = board_{i,2} = board_{i,3} \neq .\\[8pt] &\text{For some } j:\; board_{0,j} = board_{1,j} = board_{2,j} = board_{3,j} \neq .\\[8pt] &\text{Main diagonal: } board_{0,0} = board_{1,1} = board_{2,2} = board_{3,3} \neq .\\[8pt] &\text{Anti-diagonal: } board_{0,3} = board_{1,2} = board_{2,1} = board_{3,0} \neq . \end{aligned} \]

inputFormat

The input consists of 4 lines, each containing 4 characters (without spaces). Each character is one of 'W', 'B', or '.', representing a white piece, a black piece, or an empty cell respectively. There are exactly 14 pieces and 2 empty cells in total, with 7 white pieces and 7 black pieces.

outputFormat

Output a single integer – the minimum number of moves required to reach a target state, or -1 if no target state can be achieved within 10 moves.

sample

WWWW
BBWB
B.BB
W.WB

0