외계 바이러스
시간 제한2초메모리 제한1024 MB
0과 1로 이루어진 격자에서 경계의 모든 칸이 1인 직각이등변삼각형을 찾고, 한 변이 지나는 칸 수가 가장 큰 값을 구합니다.
문제
이안이는 얼마 전 토성 여행에서 토성의 위성 이아페투스를 방문했다. 그곳에서 채취한 토양 샘플을 분석하던 중 외계 바이러스를 발견했다. 이 바이러스는 평면 격자 모양의 배지에서 아주 잘 자랐다. 배지는 세로 칸, 가로 칸의 격자칸으로 이루어져 있으며, 각 격자칸은 같은 크기의 정사각형이다. 이 바이러스는 수평과 수직 방향으로 결합할 수 있었고, 여러 바이러스가 밑변과 높이가 수평, 수직인 직각이등변삼각형 모양으로 배치되면 거대한 구조를 이루었다. 이안이는 다음과 같이 바이러스 구조를 정의했다.
- 서로 다른 세 격자칸에 대해, 이 격자칸들의 중심이 이루는 삼각형 가 직각이등변삼각형이고, 이 삼각형의 빗변이 아닌 변이 배지의 세로 또는 가로 방향과 평행하다고 하자. 의 경계가 지나는 모든 격자칸에 바이러스가 있으면 를 바이러스 구조라고 하고, 의 한 변이 지나는 격자칸의 개수를 이 바이러스 구조의 크기라고 한다.
배지의 각 격자칸에 바이러스가 있는지 여부가 주어졌을 때, 모든 바이러스 구조에 대하여 크기의 최댓값을 구하여라. 바이러스 구조가 존재하지 않으면 을 출력한다.
입력
첫째 줄에 배지의 세로 크기 와 가로 크기 가 공백으로 구분되어 주어진다.
이어서 줄에 걸쳐 길이 의 0과 1로 이루어진 문자열이 주어진다. 0은 바이러스가 없는 격자칸을, 1은 바이러스가 있는 격자칸을 나타낸다. 각 와 에 대하여, 입력의 번째 줄의 번째 문자가 1이면 배지의 번째 행과 번째 열이 만나는 격자칸에 바이러스가 있고, 0이면 바이러스가 없다.
출력
바이러스 구조의 최대 크기를 정수 하나로 출력한다. 바이러스 구조가 존재하지 않으면 을 출력한다.
제한
- 주어지는 모든 수는 정수이다.