JUMPDORA - JUMPING DORA

no tags 

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 (m-1,n-1)
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]={ [0-9] , # }

 

Note: There may be no path to the destination from the Source. In such cases print -1.

C[0][0] and C[m-1][n-1] are always 0.

 

Sample Input:

1

4 4

0#03

1120

#0#0

0100

 

Sample Output:

4


hide comments
Shubham: 2015-05-18 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: 2014-04-17 09:53:33

:D okay

:D: 2014-04-17 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:2012-10-17
Time limit:1s-10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU