c++ - 在给定的 MxN 板上找到仅包含 2 种字母的最大矩形区域

Question

可能重复：查找最大子矩阵算法

---

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

给定一个在每行MxN中用字母 (az) 表示的板，我必须找到其中只有 2 种字母的最大区域。该区域必须为矩形。这是一个例子：MN

4x4:

AAAA
ABBC
BBCA
DCAA

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

Answer 1

一些想法：

1. 我认为您将不得不进行详尽的搜索。然而，一旦你找到了符合标准的面积为 A 的矩形，则无需查看任何面积小于 A 的矩形。

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

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

Answer 2

不是一个完整的工作解决方案，而是解决此问题的可能方向：

尝试用连接区域来表示棋盘，每个区域代表一个或多个包含相同字母的连接位置。然后尝试合并这些区域。