JUMPCAT - Jumping Cat

Problem Statement:

You are given a rectangular grid of order n x m (rows x columns) with an integer in each cell representing the maximum distance the cat can jump from the corresponding cell. The cat can only jump either horizontally or vertically (i.e the 4 directions around the cell). The cat can neither jump diagonally nor jump out of the grid. Find the minimum number of jumps required to reach (n-1,m-1) from (0,0), the initial position of the cat. If it’s impossible to reach (n-1,m-1), print “Impossible”.

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 n and m, the number of rows and columns in the grid followed by n lines describing the rectangular grid.

Output:

For each test case, find the minimum number of jumps required to reach the destination (n-1,m-1) from the initial position (0,0). If it’s impossible to reach the destination, print “Impossible”.

 

Input Constraints:

1 <= t <= 1000

2 <= n <= 100 

2 <= m <= 100

0 <= grid[i][j] <= 5


Sample Input:

3
5 3
122
002
310
102
333
3 2
03
11
10
3 5
20312
03213
13130

5 3
122
002
310
102
333
3 2
03
11
10
3 5
20312
03213
13

Sample Output:

5

Impossible


Added by:cegprakash
Date:2014-12-08
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: BF

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.