동전 보드 게임

N행 M열 보드가 있다. 각 칸에는 1부터 9까지의 숫자 하나 또는 구멍을 뜻하는 H가 적혀 있다. 동전은 가장 왼쪽 위 칸에서 시작하며, 이 칸은 구멍이 아니다.

한 번 이동할 때는 먼저 동전이 놓인 칸의 숫자 X를 확인한다. 그다음 위, 아래, 왼쪽, 오른쪽 중 한 방향을 골라 동전을 정확히 X칸 이동한다. 이동하는 도중에 지나치는 구멍은 무시한다.

동전이 구멍에 도착하거나 보드 밖으로 나가면 게임이 끝난다. 동전을 최대 몇 번 움직일 수 있는지 구하시오. 끝없이 움직일 수 있다면 -1을 출력한다.

첫째 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 두 값은 모두 50 이하인 자연수이다.

둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 각 문자는 1부터 9까지의 숫자 또는 H이다. H는 구멍을 뜻한다. 가장 왼쪽 위 칸은 H가 아니다.

동전을 움직일 수 있는 최대 횟수를 출력한다. 동전을 끝없이 움직일 수 있다면 -1을 출력한다.