#L2862. 纪念碑
纪念碑
题目描述 译自 BalticOI 2009 Day2 T3「Monument」
一位来自瑞典的暴发户百万富翁想要为她的家人建造一座纪念碑。所有可以追溯到的她的祖先(以及将来的后代)的名字都会被刻在纪念碑上。纪念碑是一个矩形块,顶部和底部是 a×a 的正方形,高度为 b。a,b 的值应该使四个侧面的面积,即 4ab 要尽量大。
这座纪念碑将从一个特别的 p×q×r 的矩形石块中切割出来,这个石块是由普通石块结晶化而来。也就是说,我们可以把石头看做是由 1×1×1 的单位块组成的,最后的纪念碑也将由这样的单位块组成。原石只能沿着这些单位块之间垂直于 x,y 或 z 轴切割。
原石产生了一些微孔,为空单位块。纪念碑需要精致,所以不允许包含任何微孔(空单位块)。你被给定原石的三维图,它描述了哪些单位块是空的,哪些是正常的。
你的任务是找到满足以下条件的纪念碑:
- 它可以从原石中切割出来;
- 纪念碑的四个侧面的面积,即 4ab 要尽量大。
输入格式 第一行,三个正整数 p,q 和 r。
以下 pq 行,每行 r 个字符(和一个换行符,没有多余空格)。 每个字符都是 N(正常) 或 P(空)。 第 1+(y-1)*p + (x-1) 行的第 z 个字符对应原石的单位块 (x,y,z),1 ≤ x ≤ p,1 ≤ y ≤ q,1 ≤ z ≤ r。(注:修正输入坐标映射表述,原描述“1+(yp+x-p)”存在歧义,按标准三维坐标映射逻辑修正,确保 (x,y,z) 与输入行号、列号的对应关系清晰)
输出格式 一行,4ab 的最大值。
样例 输入
3 2 5
PNNNN
PNNNN
NPPNP
PNNNP
NNNNP
PPNNP
输出
24
数据范围与提示 (无额外提示信息)