32523번 - 외계 바이러스

문제

이안이는 얼마 전 다녀온 토성 여행에서 토성의 위성 이아페투스를 방문했고, 토양 샘플을 채취해 와 분석하던 중 외계 바이러스를 발견했다. 이 외계 바이러스는 평면 격자 형태의 배지에서 아주 잘 성장했다. 배지에는 세로로 $H$칸, 가로로 $W$칸의 격자칸이 배열되어 있으며, 각 격자칸은 동일한 크기의 정사각형이다. 특이하게도 이 바이러스는 수평과 수직 방향으로 결합할 수 있었고, 여러 바이러스가 밑변과 높이가 수평, 수직인 직각이등변삼각형 모양으로 배치되었을 때 거대한 구조를 형성했다. 그래서 이안이는 바이러스 구조를 다음과 같이 정의하였다.

• 서로 다른 세 격자칸에 대해, 이 격자칸들의 중심이 이루는 삼각형 $T$가 직각이등변삼각형이고, 이 삼각형의 빗변이 아닌 변은 배지의 세로 또는 가로 방향과 평행하다고 하자. 이때 $T$의 경계가 지나는 모든 격자칸에 바이러스가 있으면, $T$를 바이러스 구조라고 하고, $T$의 한 변이 지나는 격자칸의 개수를 이 바이러스 구조의 크기라고 한다.

배지의 각 격자칸에 바이러스가 있는지 여부가 주어졌을 때, 모든 바이러스 구조에 대하여 크기의 최댓값을 구하여라. 단, 바이러스 구조가 존재하지 않으면 0ドル$을 출력한다.

입력

첫째 줄에 배지의 세로 크기 $H$와 가로 크기 $W$가 공백으로 구분되어 주어진다.

이어서 $H$줄에 걸쳐 길이 $W$의 0과 1로 이루어진 문자열이 주어진다. 0은 바이러스가 없는 격자칸을, 1은 바이러스가 있는 격자칸을 나타낸다. 각 1ドル\leq i\leq H$와 1ドル\leq j\leq W$에 대하여, 입력의 1ドル+i$번째 줄의 $j$번째 문자가 1이면 배지의 $i$번째 행과 $j$번째 열이 만나는 격자칸에 바이러스가 있고, 해당 문자가 0이면 격자칸에 바이러스가 없다.

출력

바이러스 구조의 최대 크기를 하나의 정수로 출력한다. 만약 구조가 존재하지 않는다면 0ドル$을 출력한다.

제한

• 1ドル \le H \le 750$
• 1ドル \le W \le 750$
• 주어지는 모든 수는 정수이다.

힌트