회문 단어 찾기

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

요약

문자 격자에서 한 행 전체가 팰린드롬이고 한 열 전체도 팰린드롬인 직사각형 중 넓이가 가장 큰 것의 넓이를 구합니다.

문제

대문자 알파벳으로 이루어진 직사각형 격자가 주어진다. 격자의 직사각형 영역 중 넓이가 최대인 영역을 찾아라. 이 영역에는 어떤 행 전체에 걸친 가로 회문과 어떤 열 전체에 걸친 세로 회문이 모두 있어야 한다. 회문은 거꾸로 읽어도 원래 문자열과 같은 문자열이다.

그림 1: 샘플 입력에 대한 최적해의 예시. 음영 처리된 부분 영역에서 영역 전체 행에 걸친 회문과 영역 전체 열에 걸친 회문이 강조되어 있다.

첫 줄에 두 정수 $R$ 과 $C$ ( $1 \leq R,C \leq 500$ )가 주어진다. 이어서 $R$ 개의 줄에 격자가 주어지며, 각 줄은 정확히 $C$ 개의 대문자 알파벳으로 이루어져 있다.

격자의 직사각형 영역 중 수평 방향 회문이 있는 행과 수직 방향 회문이 있는 열을 모두 포함하는 영역의 넓이 최댓값 $A$ 를 한 정수로 출력한다.