Найдите самую большую прямоугольную область, состоящую только из 2 типов букв на данной доске MxN

Question

Возможный дубликат: поиск алгоритма наибольшей подматрицы

---

Мне нужна помощь с проблемой.

Учитывая, что доска MxN представлена ​​M буквами (a-z) в каждой из строк N, мне нужно найти самую большую область, в которой есть только 2 типа букв. Область должна иметь прямоугольную форму. Вот пример:

4x4:

AAAA
ABBC
BBCA
DCAA

Вывод будет 6, потому что самая большая прямоугольная область, в которой есть только 2 типа букв, находится в верхнем углу AAA-ABB, есть только A и B (2 типа).

Answer 1

Некоторые идеи:

1. Я думаю, вам придется провести исчерпывающий поиск. Однако, как только вы нашли прямоугольник области A, который соответствует критериям, вам не нужно смотреть на прямоугольники любой области меньше A.

2. Любой прямоугольник размером 2x2 или 1x3, который содержит как минимум 3 разные буквы, не может быть частью решения. Возможно, вы могли бы сначала «пометить» эти области, а затем выполнить второе сканирование входных данных, рассматривая только прямоугольники, не включая эти отмеченные области.

3. Найдите прямоугольник 1x1, который соответствует критериям (т. Е. Каждой ячейке). Посмотрите, можно ли расширить этот прямоугольник в одном или другом направлении и при этом соответствовать критериям. Продолжайте, пока он не может быть расширен в любом направлении и по-прежнему соответствует критериям. Могут быть случаи, когда прямоугольник может быть расширен в любом направлении: вам нужно будет вернуться назад, чтобы проверить эти случаи (в вашем примере 2x2 в верхнем левом углу можно расширить в любом направлении). Для меня это звучит как проблема поиска - ознакомьтесь с некоторыми методами поиска.

Answer 2

Не полное рабочее решение, но возможное направление для решения этой проблемы:

Попробуйте представить доску в виде связанных областей , каждая область представляет одну или несколько связанных областей, содержащих одну и ту же букву. Затем попробуйте объединить регионы.