SERGRID - Grid

You are on an n x m grid where each square on the grid has a digit on it. From a given square that has digit k on it, a Move consists of jumping exactly k squares in one of the four cardinal directions. A move cannot go beyond the edges of the grid; it does not wrap. What is the minimum number of moves required to get from the top-left corner to the bottom-right corner?

Input

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input contains two space-separated integers n and m (1≤n,m≤500), indicating the size of the grid. It is guaranteed that at least one of n and m is greater than 1. The next n lines will each consist of m digits, with no spaces, indicating the n x m grid. Each digit is between 0 and 9, inclusive. The top-left corner of the grid will be the square corresponding to the first character in the first line of the test case. The bottom-right corner of the grid will be the square corresponding to the last character in the last line of the test case.

Output

Output a single integer on a line by itself representing the minimum number of moves required to get from the top-left corner of the grid to the bottom-right. If it isn’t possible, output -1.

Example

Input:
5 4 
2120
1203
3113
1120
1110 Output: 6

Added by:Joshua Kirstein
Date:2016-03-29
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:ACM SER 2015

hide comments
2018-08-14 10:34:02
AC in one Go:)
2017-01-31 06:59:34
easy bfs..
2016-11-07 10:32:00 namlunoy
DFS -> TLE

Last edit: 2016-11-07 10:32:47
2016-07-09 09:27:06
Remember --> If it isn’t possible, output -1.
2016-04-14 09:54:27 rjgames
Explanation of test case: (1 indexed)
[1,1] -> [1,3] -> [3,3] -> [3,2] -> [2,2] -> [2,4] -> [5,4]
2016-03-31 10:02:36 Sushovan Sen
Can someone please explain the test cases..

Re Thanks rjgames.

Last edit: 2016-06-17 10:01:18
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.