JUMPDORA  JUMPING DORA
Problem Statement:
Jumping Dora wants to reach her destination from the source as soon as possible.
Dora's initial position is (0,0) and the destination is (m1,n1)
If Dora is currently at (i,j), she can either move to (i,j+1) or (i,j+1+C[i][j]) or (i+1,j) or (i+1+C[i][j],j)
Dora cannot move to the blocked positions.
Note that you can jump when there are blocks in between.
Find the shortest time required to reach the destination.
Input:
The first line consists of an integer t, the number of test cases. For each test case, the first line consists of two integers m and n representing the number of rows and columns. Then follows the description of the matrix C.
Output:
For each test case find the shortest time required to reach the destination. If it is impossible, print 1.
Input Constraints:
1<=t<=100
2<=m,n<=100
C[i][j]={ [09] , # }
Note: There may be no path to the destination from the Source. In such cases print 1.
C[0][0] and C[m1][n1] are always 0.
Sample Input:
1
4 4
0#03
1120
#0#0
0100
Sample Output:
4
hide comments
Shubham:
20150518 12:19:44
finally AC easy questn reccursn gets TLE use DP.....nd my personl advice use INT_MAX in c++ carefully....i got many WA becoz of that....__..:/


cegprakash:
20140417 09:53:33
:D okay 

:D:
20140417 09:53:33
Sorry, but I feel it's too basic for classical. Adding variables to moves makes for a minor variety in the basic maze problem and it's almost the same difficulty as if C[i][j]==0 for all fields. 
Added by:  cegprakash 
Date:  20121017 
Time limit:  1s10s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 