P5964 [POI 2016] Water Park

You are given a 4-connected $n \times n$ grid graph. Each cell is either `A` or `B`. It is guaranteed that every connected component of `B` has a rectangular shape. Now you may change at most two `A` cells into `B`. Find the maximum possible size of a connected component of `B`.

The first line contains a positive integer $n$. The next $n$ lines each contain $n$ characters describing the grid.

Output one integer: the size of the largest connected component of `B`.

For $100\%$ of the testdata, $1 \le n \le 10^3$. Translated by ChatGPT 5