Сверкающие плюсы

면접 대비

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

요약

0과 1로 이루어진 n×m 행렬에서 가장 큰 십자 모양의 1 무리를 찾아 크기와 중심 좌표를 출력하고, 답이 여러 개면 행 번호가 작은 것, 그다음 열 번호가 작은 것을 고른다.

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

문제

Проказливый нюхль — маленький, пушистый черный зверек с вытянутой закругленной мордочкой, похожий на помесь крота и утконоса. Нюхль падок на все блестящее: он украдет или стянет любой сверкающий предмет, который попадется ему на глаза.

На этот раз зверек нашел матрицу $n \times m$ , состоящую из ярко сверкающих единичек и неинтересных ему нулей. Нюхль очень хочет украсть как можно больше единиц, но матрица устроена таким образом, что стянуть он может только единицы, стоящие в матрицы в виде плюса. Плюсом размера $4k + 1$ называется единица и отходящие от нее вправо, влево, вверх и вниз непрерывные последовательности единиц длины $k$ (возможно, $k = 0$ ).

Помогите зверьку украсть как можно больше единиц! Найдите в данной матрице плюс наибольшего размера.

입력

В первой строке входного файла заданы числа $n$ и $m$ --- количество строк и столбцов матрицы соответственно ( $1 \le n, m \le 5000$ ).

В каждой из последующих $n$ строк содержится $m$ символов, каждый из которых 0 или 1.

출력

В первой строке выходного файла выведите размер наибольшего плюса. В следующей строке выведите номер строки и номер столбца, в которых расположена центральная единица найденного плюса. Если ответов несколько, выведите ответ с наименьшим номером строки. Если ответов по-прежнему несколько, выведите ответ с наименьшим номером столбца.

Если в матрице отсутствуют плюсы, выведите -1.

예제2

예제 1

입력

예상 출력

9
4 4

예제 2
입력
```
3 3
010
000
001
```
예상 출력
```
1
1 2
```