행성의 스키 슬로프

그리 멀지 않은 미래에, 과학자들은 우리 태양계에서 이전까지 알려지지 않았던 행성을 하나 발견한 데 그치지 않고(Planet X 문제를 참고한다), 이제 Y 행성이라 불리는 또 하나의 행성까지 발견했다.

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

많은 이들이 기뻐할 만하게도 Y 행성은 스키를 타기에 완벽한 기후를 갖춘 것으로 밝혀졌다(짐작하겠지만 이 시대의 지구에는 더 이상 눈이 없다). Y 행성에 건설할 수 있는 가장 긴 스키 슬로프를 계산하는 프로그램을 작성한다.

왼쪽에는 첫 번째 예제가, 오른쪽에는 두 번째 예제가 표시되어 있다. 굵은 선은 스키 슬로프의 경로를 나타내며, 음영 처리된 칸은 스키 슬로프에 포함되는 칸이다.

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

채점

제출한 풀이는 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

케이스 | 배점 | 제한

$1$ |$20$| $1 \leq M, N \leq 3$

$2$ |$20$| 서로 인접한 어떤 두 칸도 높이가 같지 않다.

$3$ |$20$| 각 칸에는 자신과 높이가 같은 인접한 칸이 최대 두 개 있다.

$4$ |$40$| 추가 제한이 없다.

첫 번째 줄에 격자의 행과 열의 개수를 나타내는 두 정수 $1 \le N,M \le 7$이 주어진다. 그다음에는 각각 $M$개의 문자로 이루어진 $N$개의 줄이 주어진다. $i$번째 줄의 $j$번째 문자는 해당 칸의 높이를 나타내는 $0$에서 $9$ 사이의 숫자이다. 격자에서 같은 높이를 가진 칸은 항상 $7$개 이하이다.

올바른 스키 슬로프에 포함될 수 있는 칸 수의 최댓값을 정수 하나로 출력한다.