새 집

면접 대비

시간 제한2초메모리 제한512 MB

요약
빈 칸과 장애물로 이뤄진 N x N 격자에서 빈 칸만으로 이뤄진 정사각형의 최대 변 길이를 구한다.
난이도

쉬움10점 중 3점

유형
행렬, 동적 계획법, 완전 탐색
정답자
아직 제출이 없습니다

문제

Johan은 새 집을 짓고 싶어 하며, 집을 최대한 크게 짓고자 한다. N x N 격자 땅이 주어졌을 때, 빈 영역에 들어갈 수 있는 가장 큰 정사각형의 크기를 구하라.

입력

첫째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스는 격자 땅의 크기를 나타내는 정수 N (1 <= N <= 10)으로 시작한다. 다음 N개 줄은 각각 N개의 문자를 포함한다. 각 문자는 '.' (빈 영역) 또는 '#' (장애물)이다. 집은 빈 영역 위에 지어야 한다.

출력

각 테스트 케이스마다 빈 영역에 지을 수 있는 가장 큰 정사각형의 크기를 한 줄에 출력한다.

예제1

  1. 예제 1

    입력
    2
10
..........
.#####....
..#..###..
...##.....
...#..#...
...#...###
....######
..........
##########
#########.
5
##..#
....#
.#..#
####.
.#..#
    예상 출력
    3
2