查找给定MxN板上仅包含两种字母的最大矩形区域 [英] Find the biggest rectangular area consisting only of 2 types of letter in a given MxN board
问题描述
可能的重复：找到最大的子矩阵算法
我需要帮助解决问题。
给定一个 MxN code> M 字母（az）在每个 N 行中，我必须找到最大的区域，其中只有2字母的类型。该区域必须具有矩形形状。以下是一个例子：
4x4：
AAAA
ABBC
BBCA
DCAA
输出为6，因为最大的矩形区域只有2个类型的字母在上角AAA-ABB，只有A和B（2种类型）。
：
-
我想你必须做一个详尽的搜索。但是，一旦找到符合条件的区域A的矩形，就没有必要查看小于A的任何区域的矩形。
包含至少3个不同字母的2x2或1x3的矩形不能成为解决方案的一部分。也许你可以首先标记这些区域，然后再对输入进行第二次扫描，只考虑不包括那些标记区域的矩形。 找到1x1符合标准的矩形（即每个单元格）。看看这个矩形可以在一个方向上展开，还是符合标准。继续下去，直到它不能在任何一个方向上展开，并且仍然符合标准。可能会出现矩形可以向任一方向展开的情况：您需要回溯以检查这些情况（在您的示例中，左上角的2x2可以在任一方向上展开）。这听起来像是一个搜索问题 - 阅读了一些搜索技术。
Possible duplicate: find largest submatrix algorithm
I need help with a problem.
Given a MxN board represented with M letters (a-z) in each of the N lines, i have to find the biggest area in which there are only 2 types of letters in it. The area must have rectangular shape. Here's an example :
4x4:
AAAA
ABBC
BBCA
DCAA
The output will be 6, because the biggest rectangular area in which there are only 2 types of letters is in the upper corner AAA-ABB, there are only A and B (2 types).
Some ideas:
I think you will have to do an exhaustive search. However, once you have found a rectangle of area A that fits the criteria, there is no need to look at rectangles of any area less than A.
Any rectangle of size 2x2 or 1x3 that contains at least 3 different letters cannot be part of the solution. Perhaps you could "tag" those areas first, and then do a second scan through the input, only considering rectangles not including those tagged areas.
Find a 1x1 rectangle that fits the criteria (i.e., every cell). See if this rectangle can be expanded in one direction or the other and still fit the criteria. Continue until it cannot be expanded in either direction and still fit the criteria. There may be cases where the rectangle can be expanded in either direction: you will need to backtrack to check those cases (in your example, the 2x2 in the upper left can be expanded in either direction). This sounds like a search problem to me -- read up on some search techniques.
这篇关于查找给定MxN板上仅包含两种字母的最大矩形区域的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
