큰 정사각형

시간 제한1초메모리 제한128 MB

요약

N x N 격자의 빈 칸 한 곳에 'J'를 하나 놓아, 'J'로 이루어진 정사각형 네 꼭짓점이 최대 넓이를 갖도록 만든다.

난이도: 보통10점 중 6점
유형: 기하, 완전 탐색, 배열, 구현
정답자: 아직 제출이 없습니다

문제

농부 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인 정사각형을 완성하는 것이다.

예제5

예제 1

입력

6
J*J***
******
J***J*
******
**B***
******

예상 출력

예제 2
입력
```
2
**
**
```
예상 출력
```
0
```
예제 3
입력
```
3
JJ*
J**
***
```
예상 출력
```
1
```
예제 4
입력
```
4
J*J*
****
J*J*
****
```
예상 출력
```
4
```
예제 5
입력
```
3
*J*
J*J
*J*
```
예상 출력
```
2
```