문제
추운 겨울날, JOI 타로 군은 광장에 언 얇은 얼음을 깨며 놀기로 했다. 광장은 직사각형이고, 동서로 \(m\)칸, 남북으로 \(n\)칸, 곧 \(m \times n\)칸으로 나뉘어 있다. 얇은 얼음이 있는 칸과 없는 칸이 있다. 타로 군은 다음 규칙으로 얼음을 깨며 칸을 옮긴다.
타로 군이 얼음을 깨며 이동할 수 있는 칸 수의 최댓값을 구하는 프로그램을 작성하라. 주어지는 입력에서는 이동 방법이 20만 가지를 넘지 않는다. |
입력
입력은 다음 형식으로 주어진다.
\(m\)
\(n\)
\(A_{1,1}\) \(A_{1,2}\) \(\cdots\) \(A_{1,m}\)
\(\vdots\)
\(A_{n,1}\) \(A_{n,2}\) \(\cdots\) \(A_{n,m}\)
- 첫째 줄에 동서 방향 칸 수 \(m\)이 주어진다.
- 둘째 줄에 남북 방향 칸 수 \(n\)이 주어진다.
- 다음 \(n\)줄의 각 줄에는 \(0\) 또는 \(1\)이 공백 하나로 구분되어 \(m\)개 주어진다. 북쪽에서 \(i\)번째, 서쪽에서 \(j\)번째 칸을 \((i, j)\)라 하면, \(i+2\)번째 줄의 \(j\)번째 값은 칸 \((i, j)\)에 얇은 얼음이 있으면 \(1\), 없으면 \(0\)이다.
- \(1 \le m \le 90\)
- \(1 \le n \le 90\)
- 입력되는 값은 모두 정수이다.
출력
다음 형식으로 출력한다.
첫째 줄에 이동할 수 있는 칸 수의 최댓값을 출력한다.
예시 1
입력
3
3
1 1 0
1 0 1
1 1 0
출력
5
예시 2
입력
5
3
1 1 1 0 1
1 1 0 0 0
1 0 0 0 1
출력
5