c++ - 在给定的 MxN 板中找到仅由 2 种字母组成的最大矩形区域

Question

可能重复:find largest submatrix algorithm

---

我需要帮助解决一个问题。

给定一个 MxN 板，在每行 N 中用 M 字母 (a-z) 表示，我必须找到最大的面积其中只有两种类型的字母。该区域必须具有矩形形状。这是一个例子:

4x4:

AAAA
ABBC
BBCA
DCAA

输出会是6，因为只有2种字母的最大矩形区域在上角AAA-ABB，只有A和B(2种)。

Answer 1

一些想法:

1. 我认为您必须进行详尽的搜索。但是，一旦找到符合条件的面积 A 的矩形，就没有必要查看任何面积小于 A 的矩形。

2. 任何包含至少 3 个不同字母的 2x2 或 1x3 大小的矩形都不能作为解决方案的一部分。或许您可以先“标记”这些区域，然后对输入进行第二次扫描，只考虑不包括那些标记区域的矩形。

3. 找到符合标准(即每个单元格)的 1x1 矩形。看看这个矩形是否可以在一个方向或另一个方向上扩展并且仍然符合标准。继续，直到它不能在任何一个方向上扩展并且仍然符合标准。可能存在矩形可以在任一方向扩展的情况:您需要回溯以检查这些情况(在您的示例中，左上角的 2x2 可以在任一方向扩展)。这对我来说听起来像是一个搜索问题——阅读一些搜索技术。