Description

小白的生日就要到了, 小蓝决定送一件自己亲手做的手工艺品使自己的礼物与众不同. 具体 来说, 小蓝已经通过某种方式制作出了一个 \(p \times q \times r\) 的木块 (由 \(pqr\) 个单位小木块组成). 但由于小蓝手艺不精, 现在这个木块中的有些单位小木块是有问题的 (有裂缝、里面是空心等等), 这样的礼物小蓝是不可能直接送出去的. 于是小蓝决定在这个木块中再挖出一个 \(a \times a \times b\) 的子木块 (即要求挖出的长方体木块存在两条长度相等的相邻边), 当然这个子木块中是不能包含有问题的单位小木块的. 为了使这个木块上能包含更多的图案, 小蓝希望从所有可行的方案中挑取 \(4ab\) 的值最大的方案. 但小蓝光检测木块中哪些地方有问题就已经耗尽了体力, 作为小蓝的好友, 你能帮帮小蓝吗?

Input

每个输入文件中仅包含一个测试数据. 第一行包含三个由空格隔开的正整数,\(p, q, r\).

接下来有 \(pq\) 行, 每行包含 \(r\) 个字符, 每个字符只可能是 P (Poor) 或者 N (Nice), 表示该单位小木块有问题或者没问题. 具体的说, 第 \(1+(yp+x-p)\) 行的第 \(z\) 个字符描述的是坐标为 \((x,y,z)\) 的小木块情况.\((1 \leq x \leq p, 1 \leq y \leq q, 1 \leq z \leq r)\)

Output

输出文件仅包含一个整数, 表示最佳方案的 \(4ab\) 的值.

Sample Input

3 2 5
PNNNN
PNNNN
NPPNP
PNNNP
NNNNP
PPNNP

Sample Output

24

Data Range

对于所有的数据, 满足:\(1 \leq p, q, r \leq 150\)

Explanation

简单递推一下就可以了 (应该是一个并不需要优化的动规).

将长宽高的三种相对位置枚举一下, 然后对每种情况预处理出来每一个点向右下延伸的最长 正方形边长, 最后在每一列上动规一发就可以得到结果了.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
#define maximize(__x,__y) __x=max(__x,__y)
#define min_3(_a,_b,_c) min(min(_a,_b),_c)
#define maxn_3(_name) _name[maxn][maxn][maxn]
using namespace std;
typedef long long lli;
const int maxn = 160;

int n, m, w;
int maxn_3(a), maxn_3(b), maxn_3(f);
int c[maxn], h[maxn], l[maxn], r[maxn];

void rotate_1(void)
{
    rep(i, 1, m) rep(j, 1, n) rep(k, 1, w)
        a[i][w-k+1][j] = b[i][j][k];
    swap(n, w);
    return ;
}

void rotate_2(void)
{
    swap(n, w);
    rep(i, 1, m) rep(j, 1, n) rep(k, 1, w)
        a[k][j][m-i+1] = b[i][j][k];
    swap(m, w);
    return ;
}

int calc_height(void)
{
    c[0] = c[w+1] = -1; h[1] = 0;
    for (int i = 1, j = 1; i <= w; i++) {
        while (c[i] <= c[h[j]]) j -= 1;
        l[i] = h[j] + 1; h[++j] = i;
    }
    h[1] = w+1;
    for (int i = w, j = 1; i >= 1; i--) {
        while (c[i] <= c[h[j]]) j -= 1;
        r[i] = h[j] - 1; h[++j] = i;
    }
    int res = 0;
    rep(i, 1, w)
        maximize(res, (r[i] - l[i] + 1) * c[i]);
    return res;
}

int solve_chunk(void)
{
    rep(k, 1, w) rep(i, 1, m) rep(j, 1, n)
        f[i][j][k] = a[i][j][k] ? min_3(f[i-1][j-1][k], f[i-1][j][k], f[i][j-1][k]) + 1 : 0;
    int res = 0;
    rep(i, 1, m) rep(j, 1, n) {
        memcpy(c, f[i][j], sizeof(f[i][j]));
        maximize(res, calc_height());
    }
    return res;
}

int main(int argc, char** argv)
{
    scanf("%d%d%d", &m, &n, &w);
    rep(j, 1, n) rep(i, 1, m) rep(k, 1, w) {
        char ch = '\0'; while (ch != 'P' && ch != 'N') ch = getchar();
        a[i][j][k] = b[i][j][k] = ch == 'N' ? 1 : 0;
    }
    int res = 0;
    maximize(res, solve_chunk());
    rotate_1();
    maximize(res, solve_chunk());
    rotate_2();
    maximize(res, solve_chunk());
    // Output result.
    printf("%d\n", res * 4);
    return 0;
}