Tap Titanz at Moloco (Hard)

Time limit2sMemory limit512 MB

Summary

Given an n by n two-color board, one tap flips a whole connected same-color region; find the minimum taps to make the whole board one color.

Level: Medium7 of 10
Topics: Graph, BFS, Greedy, Dynamic programming
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples2

Example 1
Input
```
3
BWB
WBW
WWW
```
Expected output
```
2
```
Example 2
Input
```
2
BW
WB
```
Expected output
```
2
```