A2377. 礼物
编程题
提高+/省选-
知识点
题目描述
小白的生日就要到了,小蓝决定送一件自己亲手做的手工艺品使自己的礼物与众不同。具体来说,小蓝已经通过某种方式制作出了一个 $p\times q\times r$ 的木块(由 $pqr$ 个单位小木块组成)。
但由于小蓝手艺不精,现在这个木块中的有些单位小木块是有问题的(有裂缝、里面是空心等等),这样的礼物小蓝是不可能直接送出去的。于是小蓝决定在这个木块中再挖出一个 $a\times a\times b$ 的子木块(即要求挖出的长方体木块存在两条长度相等的相邻边),当然这个子木块中是不能包含有问题的单位小木块的。
为了使这个木块上能包含更多的图案,小蓝希望从所有可行的方案中挑取 $4ab$ 的值最大的方案。但小蓝光检测木块中哪些地方有问题就已经耗尽了体力,作为小蓝的好友,你能帮帮小蓝吗?
但由于小蓝手艺不精,现在这个木块中的有些单位小木块是有问题的(有裂缝、里面是空心等等),这样的礼物小蓝是不可能直接送出去的。于是小蓝决定在这个木块中再挖出一个 $a\times a\times b$ 的子木块(即要求挖出的长方体木块存在两条长度相等的相邻边),当然这个子木块中是不能包含有问题的单位小木块的。
为了使这个木块上能包含更多的图案,小蓝希望从所有可行的方案中挑取 $4ab$ 的值最大的方案。但小蓝光检测木块中哪些地方有问题就已经耗尽了体力,作为小蓝的好友,你能帮帮小蓝吗?
输入格式
每个输入文件中仅包含一个测试数据。
第一行包含三个由空格隔开的正整数,$p,q,r$。
接下来有 $pq$ 行,每行包含 $r$ 个字符,每个字符只可能是
第一行包含三个由空格隔开的正整数,$p,q,r$。
接下来有 $pq$ 行,每行包含 $r$ 个字符,每个字符只可能是
P(Poor)或者 N(Nice),分别表示该单位小木块有问题或者没问题。具体的说,第 $1+(yp+x-p)$ 行的第 $z$ 个字符描述的是坐标为 $(x,y,z)$ 的小木块情况。输出格式
输出文件仅包含一个整数,表示最佳方案的 $4ab$ 的值。
输入输出样例
输入 #1
3 2 5 PNNNN PNNNN NPPNP PNNNP NNNNP PPNNP
输出 #1
24
说明/提示
对于 $100\%$ 的数据,$0<p,q,r\le 150$,输入中至少包含一个
N。