题目描述

给定一个由字母 a, b, c, w, x, y, z 构成的矩阵，你可以将 w 改为 a 或 b，将 x 更改为 b 或 c，将 y 更改为 a 或 c，将 z 更改为 a, b 或 c。

请你求出通过更改矩阵，可以得到的由相同字母构成的最大子矩阵。

输入格式

输入包含多组测试数据。

每组测试数据第一行包含两个整数 $m$ 和 $n$，分别表示矩阵的行和列。

接下来 $m$ 行，每行包含 $n$ 个字符，描述整个矩阵，字符之间无空格。

输出格式

每组数据输出一个结果，每个结果占一行。

结果为一个整数，表示得到的最大子矩阵包含的元素个数。

样例

2 4
abcw
wxyz

3

样例解释

输入

$m=2, n=4$ 矩阵：

abcw
wxyz

可更改规则

• w → a 或 b
• x → b 或 c
• y → a 或 c
• z → a 或 b 或 c

目标

通过更改某些字符，使得存在一个子矩阵（连续的行和列），其中所有字符相同，求这个子矩阵的最大面积（元素个数）。

分析

我们可以分别考虑目标子矩阵由 a, b, c 构成的情况，取最大值。

对于目标字母 a：

• 原矩阵中已经是 a 的格子可以保留。
• w 可以改成 a。
• y 可以改成 a。
• z 可以改成 a。
• 其他字母（b, c, x）不能变成 a。

因此，对于目标 a，我们构造一个 0/1 矩阵，其中能变成 a 的格子为 1，否则为 0。然后在这个 0/1 矩阵上求最大全 1 子矩阵面积。

类似地处理目标 b 和 c。

样例计算

矩阵：

a b c w
w x y z

目标 a：

能变成 a 的格子：a, w, y, z（因为 z 可以变成 a）。 0/1 矩阵：

1 0 0 1
1 0 1 1

最大全 1 子矩阵：例如第一列两行均为 1，面积为 2；或者右下角的 2×1 或 1×2 等，最大面积为 2。

目标 b：

能变成 b 的格子：b, w, x, z。 0/1 矩阵：

0 1 0 1
1 1 0 1

最大全 1 子矩阵：第二列两行均为 1，面积为 2；或者第一行第四列和第二行第四列都是 1，但不同列。最大面积可能是 2。

目标 c：

能变成 c 的格子：c, x, y, z。 0/1 矩阵：

0 0 1 0
0 1 1 1

最大全 1 子矩阵：第二行第 2,3,4 列均为 1，但不同行？这里只有一行连续三列，面积 3。所以最大面积为 3。

因此，全局最大面积为 3，输出 3。

数据范围

• $1 \le m, n \le 1000$

算法分析

问题转化

对于每个目标字母 $ch \in \{a, b, c\}$，我们构造一个 $m \times n$ 的 0/1 矩阵 $B$，其中 $B[i][j] = 1$ 当且仅当原矩阵 $A[i][j]$ 可以通过更改变成 $ch$。

然后问题转化为：在 0/1 矩阵中求最大全 1 子矩阵的面积。

最大全 1 子矩阵

这是一个经典问题，可以用单调栈在 $O(m \times n)$ 时间内解决。

方法：

1. 对于每一列，计算从该行开始向上连续 1 的个数（即高度）。这可以通过动态规划得到：设 $h[i][j]$ 表示以 $(i,j)$ 为底向上连续 1 的最大长度。
   • 如果 $B[i][j] = 1$，则 $h[i][j] = h[i-1][j] + 1$（$i \ge 1$），否则 $h[i][j] = 0$。
2. 对于每一行 $i$，将 $h[i][1..n]$ 视为直方图的高度，用单调栈求出该直方图中最大矩形面积。这一步可以在 $O(n)$ 时间内完成。
3. 所有行中的最大面积即为该 0/1 矩阵的最大全 1 子矩阵面积。

总复杂度 $O(m \times n)$。

构造 0/1 矩阵的规则

对于每个目标字母：

• a：原字符为 a, w, y, z 时置 1。
• b：原字符为 b, w, x, z 时置 1。
• c：原字符为 c, x, y, z 时置 1。

注意：z 可以变成任意字母，所以对于任意目标字母，z 都置 1。

算法步骤

对于每组测试数据：

1. 读入 $m, n$ 和矩阵 $A$。
2. 对于目标字母集合 $\{'a','b','c'\}$：
   • 构造 0/1 矩阵 $B$。
   • 计算 $h$ 数组。
   • 对每一行用单调栈求直方图最大矩形面积，更新答案。
3. 输出最大面积。

复杂度

• 每个目标字母处理一次，共 3 次。
• 每次处理需要 $O(m \times n)$ 时间。
• 总复杂度 $O(3 \times m \times n) = O(m \times n)$，对于 $m,n \le 1000$ 可以接受。

实现细节

• 单调栈求直方图最大矩形面积的方法：
  • 遍历每个高度，维护一个单调递增栈。
  • 当当前高度小于栈顶高度时，弹出栈顶，计算以栈顶高度为高的最大矩形宽度（左边界为栈中前一个元素的下标，右边界为当前下标）。
• 注意处理边界（在高度数组末尾添加一个 0 以确保栈中所有元素被弹出计算）。
• 多组数据，需要清空数组。

样例验证

对于样例，我们已经手动验证得到最大面积为 3。

总结

本题的关键在于将问题转化为三个独立的 0/1 矩阵最大全 1 子矩阵问题，然后利用直方图单调栈方法高效求解。