문제1351--Jumping Board

### 1351: Jumping Board

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 159  통과: 28
[제출] [채점기록] [묻고답하기]

#### 문제 설명

You are given a rectangular board where each cell contains either an integer between 1 and 9, inclusive, or a hole.

Place a token into the cell in the upper left corner of the board. Now you can play a simple game. The game consists of moves, and each move looks as follows:

• Look at the number X written in the cell where your token is placed.
• Choose one of the four basic directions (up, down, left, or right).
• Move your token exactly X cells in the chosen direction. You can jump over all intermediate holes in the path.

The game ends after a move that lands the token in a hole or outside the board. Your goal is to make as many moves as possible.

The board is given as an array of strings B. Characters '1' to '9' represent cells containing the corresponding integer, and letters 'H' represent holes. The upper left corner of the board corresponds to the first character of the first element of board.

Write a program that will compute the maximum number of moves you can make on the given board. If it is possible to make an arbitrarily large number of moves, your program should output -1.

#### 입력 설명

The first line contains the number of test cases T (T ≤ 150).

For each test case, two integers R and C (1 ≤ R, C ≤ 50) will be given, with R following lines.  Each of the following lines corresponds to each element of the array B.

• Each element of B will only contain characters from the string "123456789H".
• The first character of the first element of B will not be 'H'.

#### 출력 설명

Output the answer of each test case on a separate line.

#### 입력 예시 Copy

3
3 7
3942178
1234567
9123532
1 10
2H3HH4HHH5
4 4
3994
9999
9999
2924


#### 출력 예시 Copy

5
4
-1