별(\(\texttt{*}\))과 점(\(\texttt{.}\))으로만 이루어진 \(N \times M\) 크기의 격자가 주어진다. 이 격자에서 네 변(맨 윗 줄, 맨 아랫 줄, 맨 왼쪽 열, 맨 오른쪽 열)이 모두 별로 채워진 축에 평행한 정사각형 중에서 한 변의 길이가 가장 큰 것을 찾으려 한다.

정사각형의 내부(테두리를 제외한 칸)는 별이든 점이든 상관없다. 한 변의 길이가 \(1\)인 정사각형은 별 한 칸 그 자체이며, 이 또한 (테두리가 별인) 유효한 정사각형으로 본다.

예를 들어 다음 격자에서는 바깥 테두리 전체가 별인 한 변의 길이가 \(5\)인 정사각형이 가장 크다.

*****
*...*
*.*.*
*...*
*****

네 변이 모두 별인 정사각형의 최대 한 변의 길이를 출력하라. 그러한 정사각형이 하나도 없으면(즉 격자에 별이 한 칸도 없으면) \(0\)을 출력한다.

\(1 \le N, M \le 1{,}500\)

격자의 각 칸은 \(\texttt{*}\) 또는 \(\texttt{.}\) 이다.

첫째 줄에 두 정수 \(N\), \(M\) (\(1 \le N, M \le 1{,}500\)) 이 공백으로 구분되어 주어진다.

다음 \(N\)개의 줄에 각각 길이 \(M\)인 문자열이 주어진다. 각 문자는 별을 뜻하는 \(\texttt{*}\) 또는 빈 칸을 뜻하는 \(\texttt{.}\) 이다.

네 변이 모두 별로 이루어진 축에 평행한 정사각형 중 한 변의 길이가 가장 큰 것의 한 변의 길이를 한 줄에 출력한다. 그러한 정사각형이 없으면 \(0\)을 출력한다.

riseoj 작성

출처 Original