살얼음 건너기

시간 제한1초메모리 제한128 MB

요약

얇은 얼음 칸으로 이루어진 m×n 격자에서 아무 칸에서나 시작해 깨지지 않은 얼음만 밟으며 지나갈 수 있는 최대 칸 수를 구한다.

난이도: 어려움10점 중 8점
유형: 그래프, DFS, 백트래킹, 완전 탐색
정답자: 아직 제출이 없습니다

문제

어느 추운 겨울날, 넓은 광장에 언 살얼음을 깨뜨리며 노는 놀이를 하려고 한다. 광장은 직사각형 모양이며, 동서 방향으로 $m$ 칸, 남북 방향으로 $n$ 칸, 즉 $m \times n$ 개의 칸으로 나뉘어 있다. 각 칸에는 살얼음이 있는 칸과 없는 칸이 있다. 다음 규칙에 따라 살얼음을 깨뜨리며 칸을 이동한다.

살얼음이 있는 어느 칸에서든 살얼음 깨기를 시작할 수 있다.
동서남북 중 한 방향으로 인접하고, 아직 깨지지 않은 살얼음이 있는 칸으로 이동할 수 있다.
이동한 칸의 살얼음은 반드시 깨진다.

이때 시작한 칸을 포함하여, 살얼음을 깨뜨리며 지나갈 수 있는 칸 수의 최댓값을 구하는 프로그램을 작성하시오. 단, $1 \le m \le 90$ , $1 \le n \le 90$ 이다. 주어지는 입력에서 가능한 이동 경로의 수는 20만 가지를 넘지 않는다.

입력

입력은 $n+2$ 개의 줄로 이루어진다. 첫째 줄에는 정수 $m$ 이, 둘째 줄에는 정수 $n$ 이 주어진다. 셋째 줄부터 $n+2$ 째 줄까지 각 줄에는 $0$ 또는 $1$ 이 공백으로 구분되어 $m$ 개씩 주어지며, 해당 칸에 살얼음이 있는지를 나타낸다. 북쪽에서 $i$ 번째, 서쪽에서 $j$ 번째 칸을 $(i, j)$ 라 하면 ( $1 \le i \le n$ , $1 \le j \le m$ ), 제 $i+2$ 째 줄의 $j$ 번째 값은 칸 $(i, j)$ 에 살얼음이 있으면 $1$ , 없으면 $0$ 이다.

출력

지나갈 수 있는 칸 수의 최댓값을 출력하시오.

예제2

예제 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
```