P3331 [ZJOI2011] Gift

Xiaolan wants to give a unique handmade present for Xiaobai’s upcoming birthday. Specifically, Xiaolan has somehow made a $p\times q\times r$ wooden block (composed of $p q r$ unit cubes). However, due to lack of skill, some unit cubes inside this block are defective (cracks, hollow inside, etc.), so Xiaolan cannot give it as-is. Xiaolan decides to carve out an $a\times a\times b$ sub-block from it (i.e., the carved rectangular block must have two adjacent edges of equal length). Of course, this sub-block must not contain any defective unit cubes. To allow more patterns on the block, Xiaolan wants to choose, among all feasible plans, the one that maximizes the value of $4ab$. But Xiaolan is exhausted after checking which unit cubes are defective. As Xiaolan’s friend, can you help?

Each input file contains exactly one testdata. The first line contains three positive integers $p, q, r$ separated by spaces. Then there are $p q$ lines, each containing $r$ characters. Each character is either `P` (Poor) or `N` (Nice), indicating whether the corresponding unit cube is defective or not. Specifically, in line number $1 + (y p + x - p)$, the $z$-th character describes the cube at coordinate $(x, y, z)$.

The output contains exactly one integer: the maximum possible value of $4ab$.

For $100\%$ of the testdata, $0 < p, q, r \le 150$, and the input contains at least one `N`. Translated by ChatGPT 5