플래닛백

그리 멀지 않은 미래에 연구자들은 우리 태양계에서 이전에 알려지지 않았던 행성을 하나 발견했을 뿐만 아니라(Planet X 문제 참고), 이제는 행성 Y라고 불리는 행성을 하나 더 발견했다.

연구자들은 행성 Y의 지형이 어떻게 생겼는지에 관심이 있으며, 이를 매우 정밀하게 측정하는 데 성공했다. 표면은 $N \times M$ 격자로 나타내고, 각 칸에는 0과 9 사이의 측정된 높이가 있다.

많은 사람이 기뻐할 만하게도 행성 Y는 스키를 타기에 완벽한 기후를 가지고 있다(짐작하겠지만 그 시점에 지구에는 더 이상 눈이 없다). 행성 Y에 지을 수 있는 가장 긴 스키 슬로프를 계산하는 프로그램을 작성하시오.

스키 슬로프는 칸들의 연속된 나열이어야 하며, 나열에서 이웃한 두 칸은 변이나 꼭짓점을 공유한다(아래 그림 참고). 또 나열의 각 칸은 바로 앞 칸보다 높이가 높아서는 안 된다. 따라서 원칙적으로 스키 슬로프의 모든 칸이 같은 높이인 것도 허용된다. 같은 칸을 여러 번 사용할 수는 없지만, 아래 두 번째 예시처럼 스키 슬로프가 꼭짓점에서 자기 자신과 교차할 수는 있다.

첫째 줄에 두 정수 $1 \le N,M \le 7$이 주어진다. 이는 격자의 행과 열의 수이다. 이어서 $N$개의 줄이 주어지고, 각 줄에는 $M$개의 문자가 있다. $i$번째 줄의 $j$번째 문자는 칸의 높이에 해당하는 0과 9 사이의 숫자이다. 격자에서 같은 높이를 가진 칸은 절대 7개를 넘지 않는다.

프로그램은 하나의 정수를 출력한다. 이는 유효한 스키 슬로프에 포함될 수 있는 칸의 최대 개수이다.