#P4348. [POI2016]Park wodny

    ID: 3554 传统题 2000ms 256MiB 尝试: 141 已通过: 22 难度: 7 上传者: 标签>CF2300提高+/省选-洪水填充缩点暴力枚举保留最优候选鸣谢Claris

[POI2016]Park wodny

[POI2016] Park wodny

题目描述

给出一个 n×nn\times n 的四连通的网格图,每个格子要么是 A,要么是 B,保证 B 的连通块的形状都是矩形。

现在你最多可以把两个 A 变成 B,问最大的 B 的连通块有多大。

输入格式

第一行包含一个正整数 nn。

接下来 nn 行,每行 nn 个字符,表示这个网格图。

输出格式

输出一行一个整数,即最大的 B 的连通块的大小。

样例 #1

样例输入 #1

5
BBBAB
BBBAB
AAAAA
BBABA
BBAAB

样例输出 #1

14

提示

对于 100%100\% 的数据,1≤n≤1031\le n\le 10^3。