동전 보드 게임

문제

1부터 9까지의 숫자와 구멍(H)이 적힌 N×M 직사각형 보드에서 동전 게임을 한다. 동전은 가장 왼쪽 위 칸(1행 1열)에서 시작하며, 현재 있는 칸에 적힌 수만큼 상, 하, 좌, 우 중 한 방향으로 이동할 수 있다. 이동한 칸이 구멍(H)이거나 보드 밖이면 게임이 끝난다.

동전이 보드 위에서 움직일 수 있는 최대 횟수를 구하라. 동일한 칸을 여러 번 방문하여 무한히 이동할 수 있는 경우에는 -1을 출력하라.

입력

첫째 줄에 보드의 세로 크기 N과 가로 크기 M이 공백으로 구분되어 주어진다. (1 ≤ N, M ≤ 50)
둘째 줄부터 N개의 줄에 걸쳐 보드의 상태가 주어진다. 각 줄은 길이가 M인 문자열이며, 각 칸은 1부터 9까지의 숫자 또는 H(구멍) 중 하나이다. 시작 칸(1행 1열)은 항상 숫자임이 보장된다.

출력

동전이 이동할 수 있는 최대 횟수를 출력하라. 단, 무한히 이동할 수 있는 경우에는 -1을 출력하라.

입출력 예시

입력 1

3 3
124
9H3
112

출력 1

3

입력 2

1 1
9

출력 2

-1

입력 3

4 5
12345
54321
5H432
12345

출력 3

6

입력 4

4 4
3456
HHHH
HHHH
HHHH

출력 4

4