Tap Titanz at Moloco (Hard)

Some Moloco employees play clicker games like Tap Titanz.

In Tap Titanz you are given an $n \times n$ board whose cells are black or white. Two cells are adjacent if they share an edge. Two cells are connected if you can walk from one to the other through adjacent cells that all have the same color, so connected cells always have the same color.

When the player taps a cell, that cell changes to the opposite color, and so do its adjacent cells of the same color, and their adjacent cells of the same color, and so on. In other words, the tapped cell and every cell connected to it change color at the same instant.

The game ends when every cell has the same color, all black or all white. The goal is to tap as few times as possible.

The first line contains an integer $n$ ($1 \le n \le 25$).

Each of the next $n$ lines contains a string of length $n$ that describes one row of the board, from top to bottom. Each string consists only of 'B' for a black cell and 'W' for a white cell.

Print the minimum number of taps needed to make every cell have the same color.