Square Pen

면접 대비

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

요약

장애물과 빈 칸으로 이루어진 s x s 격자가 주어질 때, 장애물이 하나도 없는 가장 큰 정사각형 부분 격자를 찾아 넓이를 출력한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 행렬, 배열, 구현
정답자: 아직 제출이 없습니다

문제

You want to create a huge square pen for your animals in one of your fields. That way they can enjoy the sunlight instead of staying pent up in their dusty barn all year. Your field is still messy though. You don’t want to clean it, you just want to build the biggest possible square pen without any junk in it. Given the layout of your field, determine the area of the largest square pen you can make.

입력

The first line will contain a single integer n that indicates the number of data sets that follow. Each data set will start with a single integer s denoting the side length of your square field. The next s lines will consist of the layout of your field, with “#” denoting an obstacle, and ‘.’ denoting a free space.

출력

For each test case, output the area of the largest square pen you can make without it having any obstacles inside of it.

예제1

예제 1

입력

2
5
...##
##...
.....
#....
#..##
6
...##.
##..##
..###.
#.....
#..##.
..##..

예상 출력

9
4