最大F矩形问题

题目描述

有一天，小猫 rainbow 和 freda 来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。

这片土地被分成 $N \times M$ 个格子，每个格子里写着 R 或者 F，R 代表这块土地被赐予了 rainbow，F 代表这块土地被赐予了 freda。

现在 freda 要在这里卖萌。。。它要找一块矩形土地，要求这片土地都标着 F 并且面积最大。

但是 rainbow 和 freda 的 OI 水平都弱爆了，找不出这块土地，而蓝兔也想看 freda 卖萌（她显然是不会编程的……），所以它们决定，如果你找到的土地面积为 $S$，它们将给你 $3 \times S$ 两银子。

输入格式

第一行包括两个整数 $N, M$，表示矩形土地有 $N$ 行 $M$ 列。

接下来 $N$ 行，每行 $M$ 个用空格隔开的字符 F 或 R，描述了矩形土地。

每行末尾没有多余空格。

输出格式

输出一个整数，表示你能得到多少银子，即 $(3 \times \text{最大F矩形土地面积})$ 的值。

输入输出样例 #1

输入样例

5 6
R F F F F F
F F F F F F
R R R F F F
F F F F F F
F F F F F F

输出样例

45

限制条件

• $1 \le N, M \le 1000$

时间限制

1秒

空间限制

64MB

样例解释

给定一个 $5 \times 6$ 的网格：

行1: R F F F F F
行2: F F F F F F
行3: R R R F F F
行4: F F F F F F
行5: F F F F F F

我们需要找到最大的全 F 矩形区域。

观察网格：

• 第1行：从第2列到第6列是 F（5个）
• 第2行：全部是 F（6个）
• 第3行：从第4列到第6列是 F（3个）
• 第4行：全部是 F（6个）
• 第5行：全部是 F（6个）

最大全 F 矩形：

• 位于第2行到第5行，第1列到第6列
• 这是一个 $4 \times 6$ 的矩形
• 面积 = $4 \times 6 = 24$

但仔细检查：第3行第1列到第3列是 R，所以第1列不能包含在内。

实际上最大的全 F 矩形是：

• 行：第4行和第5行（2行）
• 列：第1列到第6列（6列）
• 面积 = $2 \times 6 = 12$

但题目输出是45，对应面积 $S = 15$（因为 $3 \times 15 = 45$）。

寻找面积15的矩形：

• 可以是 $3 \times 5 = 15$
• 或者 $5 \times 3 = 15$

检查网格： 最大全 F 矩形实际上是：

• 行：第4行和第5行（2行）→ 第4行全部是 F，第5行全部是 F
• 列：第1列到第6列（6列）
• 但第3行第1-3列是 R，所以第1-3列不能包含第3行，但第4-5行第1-3列是 F

实际上，最大的全 F 矩形是： 以每个位置为底的 F 柱状图高度：

行1: 0 1 1 1 1 1
行2: 1 2 2 2 2 2  
行3: 0 0 0 3 3 3
行4: 1 1 1 4 4 4
行5: 2 2 2 5 5 5

第4列到第6列，从第3行到第5行：

• 第3行：高度为3
• 第4行：高度为4
• 第5行：高度为5 但第3行第4-6列上方没有 R 阻挡。

以第5行为例，第4-6列形成高度为5的矩形，宽为3，面积=15。

所以最大面积为15，输出 $3 \times 15 = 45$。