Coin Flip Chessboard

In this problem, you are given an (n \times n) chessboard. Each cell of the chessboard contains a coin that has two sides: one black and one white. Initially, some coins are black‐side up and some are white–side up. Your task is to determine the minimum number of moves required to make all coins show the same color (either all black or all white).

A move is defined as selecting any coin on the board and flipping it. When a coin is flipped, its adjacent coins (up, down, left, and right) are also simultaneously flipped. Flipping a coin means changing its face (black becomes white and white becomes black). If it is impossible to achieve a uniform board, output -1.

The problem can be reformulated in modulo (2) arithmetic; representing black as 1 and white as 0, a flip toggles the corresponding cell and its four neighbors (if they exist). You are allowed to attempt to achieve either target state: all coins 0 (white) or all coins 1 (black), and you should find the minimal moves among the two possibilities.

inputFormat

The first line contains a single integer (n) ((1 \le n \le 6)), indicating the size of the chessboard. Each of the following (n) lines contains (n) space-separated characters. Each character is either 'B' (representing a coin with the black side up) or 'W' (representing white side up).

outputFormat

Output a single integer representing the minimum number of moves required to make all coins show the same color. If it is impossible, output -1.

sample

2
B B
B B

0