cho.sh

Coin Board Game

A coin on a grid jumps exactly the digit on its cell in one of four directions; find the maximum number of moves before it leaves the board or hits a hole, or -1 if it can move forever.

Medium7Dynamic programmingDFSGraphMatrixInterviewNo attempts yetTime limit2sMemory limit512 MB

Problem

A board has N rows and M columns. Each cell contains either a digit from 1 to 9 or H, which represents a hole. A coin starts on the top-left cell, and that cell is never a hole.

On each move, look at the digit X written on the coin's current cell. Choose one of the four directions: up, down, left, or right. Then move the coin exactly X cells in that direction. Holes passed over during the move are ignored.

If the coin lands in a hole or moves outside the board, the game ends. Find the maximum number of moves that can be made. If it is possible to keep moving forever, print -1.

Input

The first line contains two positive integers N and M, the board's height and width. Both are at most 50.

Each of the next N lines contains the board state. Each character is either a digit from 1 to 9 or H. H means a hole. The top-left cell is not H.

Output

Print the maximum number of moves the coin can make. If the coin can move forever, print -1.