ZOJ Problem Set - 3146
Heidi and Sammy are lost among the trees and begging for a program to find their shortest way home.
Fortunately, our two puppies find themselves in a mathematical forest where the trees are planted on a square grid and where each tree has the shape of a number. Heidi and Sammy remember that from a tree with number n they should choose a direction - north, south, east, or west - and walk in this direction until they reach the n'th tree, at which time they will either have reached the single tree shaped like the number 0 - their home - or they need to make their next move, based on the shape of the tree they just reached. Needless to say, an invisible fence safely keeps our forlorn puppies inside the forest.
There are multiple test cases for this problem. The first line of each case contains four positive integers n, m, r, and c, separated by white space. n and m are the dimensions of the grid, each not exceeding 30. Each of the next n lines contains m nonnegative int values, separated by white space, which are the numbers for the trees in this row of the grid. Exactly one number in the grid will be zero. r and c are the row and column of the puppies' initial position.
If the puppies can reach their home, the output of your program is the minimal number of steps required to get home, i.e., the sum of the tree shapes forming the shortest path. Otherwise your program prints No solution.
4 3 1 1 2 2 3 3 6 4 2 6 3 3 2 0
In this example the puppies start at 1,1 - the top left of the grid - and move 2 trees east to 1,3 and from there 3 trees south to 4,3 - their home.
Source: Northeast North Ameriaca Regional Contest 2007