주어진는 M × N 보드에

Question

가능한 중복 편지의 2 종류로 구성된 가장 큰 사각형 영역 찾기 : find largest submatrix algorithm

---

나는이 문제에 도움이 필요합니다.

가 N 라인 각각 M 문자 (A-Z)으로 표시되는 MxN 보드 주어 난 글자의 2 종류가있는 큰 영역을 찾을 수있다. 영역은 직사각형이어야합니다. 여기서 예이다 : 가장 큰 직사각형 영역이되는 문자의 2 종류가 있으므로 상단 모서리 AAA-ABB에,

4x4: 

AAAA 
ABBC 
BBCA 
DCAA 

출력 될 것이다 (6)가있는 단지 및 B (2 종) .

Answer 1

하지 완벽한 작업 솔루션,하지만이 문제를 해결하기위한 가능한 방향 :

이 연결 지역의 측면에서 보드를 대표하는 시도는, 각 지역은 같은 문자를 포함하는 하나 개 이상의 연결된 위치를 나타내는. 그런 다음 지역을 결합 해보십시오.

Answer 2

몇 가지 아이디어 :

1. 난 당신이 철저한 검색을 수행 할 것이라 생각합니다. 그러나 기준에 맞는 영역 A의 직사각형을 찾으면 A 미만의 직사각형을 볼 필요가 없습니다.

2. 3 자 이상의 문자가 포함 된 직사각형 크기 2x2 또는 1x3 솔루션의 일부가 될 수 없습니다. 아마도 해당 영역에 "태그를 추가"한 다음 입력을 통해 두 번째 스캔을 수행하고 태그가있는 영역을 포함하지 않는 사각형 만 고려하면됩니다.

3. 기준 (즉, 모든 셀)에 맞는 1x1 직사각형을 찾습니다. 이 사각형을 한 방향으로 확장 할 수 있는지 또는 다른 방향으로 확장 할 수 있는지, 여전히 기준에 맞는지 확인하십시오. 어느 방향으로도 확장 할 수 없으며 여전히 기준에 맞을 때까지 계속하십시오. 직사각형을 어느 방향 으로든 확장 할 수있는 경우가 있습니다. 이러한 경우를 확인하기 위해 역 추적해야합니다 (예를 들어, 왼쪽 상단의 2x2는 어느 방향 으로든 확장 가능). 이것은 저에게 수색 문제 같이 소리가 난다 - 약간 수색 기술에 읽는.