Perica i Jovica su nedavno saznali za drevnu kinesku igru Go i odlučili da odigraju partiju. Igra im se toliko svidela da nisu ni proučili sva pravila detaljno, već igraju po svojim, malo izmenjenim, pravilima.

Perica i Jovica igraju na tabli dimenzija N x N. Perica je beli igrač i njegovi kamenčići su bele boje, dok Jovica ima kamenčiće crne boje. Igrači igraju naizmenično, a u svakom potezu igrač, čiji je red, postavlja jedan svoj kamenčić na slobodno polje.

Svako polje je susedno sa najviše četiri polja - gore, dole, levo i desno. Polja na ivicama table imaju tri, a ćopkovi samo dva susedna polja. Prazno polje susedno nekom polju na kome se nalazi kamenčić predstavlja jednu slobodu tog kamenčića. Dva susedna kamenčića iste boje su povezana, a svi međusobno povezani kamenčići čine jednu grupu. Takođe, broj praznih susednih polja svih kamenčića jedne grupe predstavlja broj sloboda te grupe. Ukoliko, posle nekog poteza, neke protivničke grupe izgube sve svoje slobode, svi kamenčići tih grupa se uklanjaju. Ako postavljanje kamenčića dovodi do gubitka slobode i protivničkih i svojih grupa, uklanjaju se samo protivničke grupe. Međutim, potez može da dovede i do uklanjanja sopstvenih kamenčića ako se tim potezom gube slobode samo sopstvene grupe.

Partija se zahuktala i na potezu je Perica - beli igrač. Perica želi da odigra takav potez da nakon postavljanja belog kamenčića i eventualnog uklanjanja grupa, razlika belih i crnih kamenčića bude što veća. Odnosno, ako sa b označimo broj belih kamenčića, a sa c broj crnih kamenčića, Perica želi da izraz b - c bude što veći. Odredite kolika će ova razlika da bude ako Perica odigra najbolji potez.

Ulaz.

(Ulazni podaci se uqitavaju iz datoteke go.in) U ulaznoj datoteci se u prvom redu nalazi jedan broj N (1 ≤ N ≤ 1.000), koji predstavlja dimenzije table. U sledećih N redova nalazi se po N znakova 'B', 'C' ili '.', koji predstaljaju stanje table u trenutku kad je Perica na potezu. Svaki znak 'B' predstavlja po jedan beli kamenčić, svaki znak 'C' predstavlja po jedan crni kamenčić, dok znak '.' predstavlja prazno polje. Postojaće bar jedno prazno polje i na tabli neće biti nijedna grupa koja nema nijednu slobodu.

Izlaz.

(Izlazni podaci se ispisuju u datoteku go.out) U prvom i jedinom redu izlazne datoteke ispisati razliku belih i crnih kamenčića nakon najboljeg poteza.

Primer 1.

7
.BBBB..
BCCCCBC
BCB.CBC
BCCCCBB
BBBBB..
....B.C
CB.....

16

Objašnjenje. Na tabli se nalazi 19 belih i 14 crnih kamenčića. Od svih poteza, najbolji je postavljanje belog kamenčića na polje u trećem redu i četvrtoj koloni, što dovodi do toga da jedna bela i jedna crna grupa gube sve svoje slobode, pa se uklanja samo crna grupa od 10 kamenčića. Nakon ovog poteza, na tabli se nalazi 20 belih i 4 crna kamenčića, pa je razlika 16.

#include <cstdio>
#include <queue>

using namespace std;

const int kMaxSize = 1001;
const int kInfinity = 1000000000;

char table[kMaxSize][kMaxSize];
int visited[kMaxSize][kMaxSize];
int blackValues[kMaxSize][kMaxSize], whiteValues[kMaxSize][kMaxSize];
int componentSize[kMaxSize * kMaxSize];
int n, blackCount, whiteCount = 1, sol, bfsCount;
int bestBlack, bestWhite = kInfinity; 
queue<pair<int, int> > bfsQueue;
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1}; 

bool isConnected(int row, int column, int type)
{
    return row >= 0 && row < n && column >= 0 && column < n && table[row][column] == type;   
}

void bfs(int row, int column, char stone)
{
    pair<int, int> liberty(-1, -1);
    int liberties = 0, groupSize = 0;
    bfsCount++;
    bfsQueue.push(make_pair(row, column));
    visited[row][column] = bfsCount;
    while (!bfsQueue.empty())
    {
        pair<int, int> current = bfsQueue.front();
        bfsQueue.pop();       
        groupSize++;
        for (int i = 0; i < 4; i++)
        {
            if (visited[current.first + dr[i]][current.second + dc[i]] != bfsCount)
            {
                if (isConnected(current.first + dr[i], current.second + dc[i], stone))
                {
                    bfsQueue.push(make_pair(current.first + dr[i], current.second + dc[i])); 
                    visited[current.first + dr[i]][current.second + dc[i]] = bfsCount;  
                }
                if (isConnected(current.first + dr[i], current.second + dc[i], '.'))
                {
                    visited[current.first + dr[i]][current.second + dc[i]] = bfsCount;
                    liberty = make_pair(current.first + dr[i], current.second + dc[i]); 
                    liberties++;  
                }      
            }
        }         
    } 
    componentSize[bfsCount] = liberties;
    if (liberties == 1)
    {
        if (stone == 'C')
        {
            blackValues[liberty.first][liberty.second] += groupSize;   
        }       
        else
        {
            whiteValues[liberty.first][liberty.second] += groupSize;   
        }
    }
    
}

int main()
{
    freopen("go.in", "r", stdin);
    freopen("go.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%s", table[i]);   
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (table[i][j] != '.')
            {
                if (visited[i][j] == 0)
                {
                    bfs(i, j, table[i][j]);   
                }
                if (table[i][j] == 'C') 
                {
                    blackCount++;   
                }   
                else
                {
                    whiteCount++;   
                }
            }
        }   
    }
    
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (table[i][j] == '.')
            {
                if (blackValues[i][j] > bestBlack)
                {
                    bestBlack = blackValues[i][j];  
                }    
                if (whiteValues[i][j] == 0)
                {
                    bool free = false;
                    for (int k = 0; k < 4; k++)
                    {
                        if (isConnected(i + dr[k], j + dc[k], '.'))
                        {
                            free = true;
                        }  
                    }
                    if (free)
                    {
                        whiteValues[i][j] = -1;   
                    }
                }
                if (blackValues[i][j] == 0)
                {
                    bool connects = false;
                    for (int k = 0; k < 4; k++)
                    {
                        if (isConnected(i + dr[k], j + dc[k], 'B') &&
                            componentSize[visited[i + dr[k]][j + dc[k]]] > 1)
                        {
                            connects = true;   
                        }
                    }
                    if (connects)
                    {
                        whiteValues[i][j] = -1;  
                    }
                    if (whiteValues[i][j] < bestWhite)
                    {
                        bestWhite = whiteValues[i][j] + 1;   
                    }
                }
            }
        }
    }
    sol = bestBlack > 0 ? whiteCount - blackCount + bestBlack: 
            whiteCount - blackCount - bestWhite;
    printf("%d\n", sol);
    return 0;   
}