Palindromic Word Search

시간 제한6초메모리 제한1024 MB

요약

어떤 행 전체가 회문이고 어떤 열 전체도 회문인 부분 직사각형 중 넓이가 최대인 것을 찾는다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 행렬, 완전 탐색
정답자: 아직 제출이 없습니다

문제

Given a rectangular grid of uppercase letters, find a rectangular region of the grid of maximum possible area such that there is a horizontal palindrome spanning some row of the rectangular region and a vertical palindrome spanning some column of the rectangular region. Recall a palindrome is a string that equals its own reversal.

Figure 1: Illustration of optimal solutions to the sample inputs. In the shaded subregions, a palindrome spanning an entire row of the region and a palindrome spanning an entire column of the region are highlighted.

입력

The first line contains two integers $R$ and $C$ ( $1 \leq R,C \leq 500$ ). Then next $R$ lines describe the grid, each containing exactly $C$ uppercase letters.

출력

Output a single integer $A$ indicating the largest area of a rectangular region of the grid such that there is a horizontal palindrome spanning some row and a vertical palindrome spanning some column of the rectangular region.

예제3

예제 1
입력
```
4 5
APPLE
BOBBY
KAYAK
REBEL
```
예상 출력
```
15
```
예제 2
입력
```
2 6
ABCCDE
PRCDEE
```
예상 출력
```
4
```
예제 3
입력
```
4 6
BANANA
BERGEN
CANNOT
FELLOW
```
예상 출력
```
15
```