큰 정사각형

아직 제출이 없습니다시간 제한1초메모리 제한128 MB

문제

농부 John의 소들이 농부 Bob의 소들과 시합을 벌인다. 들판에는 $N \times N$개의 격자점이 찍혀 있고 ($2 \le N \le 100$), 두 무리의 소들은 각자 서로 다른 격자점 위에 한 마리씩 서 있다. 두 소가 같은 격자점에 설 수는 없다. 각 무리의 목표는 자기 무리의 소 네 마리를 네 꼭짓점으로 하는 가장 큰 정사각형(변이 반드시 격자선과 평행할 필요는 없다)을 만드는 것이다.

농부 John의 소 Bessie를 제외한 모든 소의 위치는 이미 정해져 있다. Bessie는 현재 비어 있는 격자점 중 한 곳에 세워야 한다. Bessie를 세운 뒤 농부 John의 소들이 만들 수 있는 가장 큰 정사각형의 넓이를 구하여라. (가장 큰 정사각형이 반드시 Bessie를 포함할 필요는 없다.)

입력

  • 첫째 줄: 정수 $N$.
  • 둘째 줄부터 $N+1$째 줄까지: $i+1$째 줄은 들판의 $i$번째 행을 나타내는 $N$개의 문자로 이루어진다. 각 문자는 농부 John의 소를 뜻하는 J, 농부 Bob의 소를 뜻하는 B, 빈 격자점을 뜻하는 * 중 하나이다. 빈 격자점은 항상 하나 이상 존재한다.

출력

  • 첫째 줄: 농부 John의 소들이 만들 수 있는 가장 큰 정사각형의 넓이. 어떤 정사각형도 만들 수 없으면 0.

힌트

샘플에서 만약 Bessie가 농부 Bob의 소가 있는 격자점에 설 수 있었다면 넓이가 8인 정사각형을 만들 수 있었다. 하지만 두 소가 같은 격자점에 설 수는 없으므로, Bessie가 할 수 있는 최선은 3행 3열에 서서 왼쪽 위의 넓이 4인 정사각형을 완성하는 것이다.