Min Jumps

Easy

0/40

Average time to solve is 15m

Contributed by

13 upvotes

Asked in companies

Problem statement

You live in a Ninja town which is in the form of a N * M grid. In this town, people travel from one place to another by jumping over the buildings which are present in each cell of the grid. It is Christmas eve, and Santa wants to give gifts and chocolates to the kids who live in the building which is present at the cell (N - 1, M - 1). Initially, Santa is present on cell (0, 0). Since Santa is in a hurry, help him find a path from starting point to the endpoint with the least amount of time.

The Santa may go only from one building to any of its adjacent buildings which is present either to the right or to the bottom or bottom right cell i.e. if the current position is (x, y), he may go to (x + 1, y + 1) or (x + 1, y) or (x, y + 1) given that the new coordinates are in the grid. The time taken to reach from one building to another is equal to the absolute difference between the heights of buildings.

Note:

1. The heights of the buildings are positive.
2. Santa starts from the cell (0, 0) and he has to reach the building (N - 1, M - 1).
3. Santa cannot leave the grid at any point of time.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains an integer T denoting the number of test cases. Then T lines follow:

The first line of each test case contains two space-separated integers N and M, where N = number of rows in the given matrix and M = number of columns in the given matrix.    

Then N lines follow for each test case:
Each line contains M space-separated integers.

For more clarity please refer to the sample input.

Output Format:

The only line of output of each test case consists of an integer X, denoting the minimum time required to reach the last cell.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10^2
1 <= N <= 10^2
1 <= M <= 10^2
1 <= Height <= 10^5

Time Limit: 1sec

Sample Input 1:

Sample Output 1:

8
3

Explanation For Sample Input 1:

For test case 1:

One of the possible ways is to go from (0, 0) to (1, 1) to (2, 2). 
So the total cost will be abs(1 - 5) + abs(5 - 9) = 8. 

For test case 2:

Optimal was to go from (0,0) to (1,1) is (0,0) --> (1,1) with the 
cost abs(1-4) = 3.

Sample Input 2:

Sample Output 2:

0
2

Hint 1

Hint 2

Try all possible combinations.

Approaches (2)

Approach 1

Approach 2

Recursive

Since we want to try all the possible combinations and then find the answer, recursion is a good way to do it.
Let the name of the given matrix be ARR[][] where ARR[X][Y] denotes the height of the building at coordinates X, Y.
Let us suppose that we have a recursive function findMinCost() which takes X, Y as the input and returns the minimum cost to reach from start to end.
Now at every step, we have 3 options, to go right or bottom or bottom right. So we can find the cost by visiting each cell and find the minimum cost.
Let rightCost = INT_MAX initially. To visit the right building we will have to go to cell (X, Y + 1). If it is safe to visit the right cell then rightCost = findMinCost(X, Y + 1) + abs(ARR[X][Y] - ARR[X][Y + 1]).
Similarly, we can find the cost of moving down and bottom right. And finally, the answer will be the minimum of all the 3 calculated values.

Time Complexity

O(3^(N*M)), where N is the number of rows and M is the number of columns.

In the recursion call, there will be 3 calls for each cell of the matrix so it leads to the time complexity of 3^(N*M) for N rows and M columns.

Space Complexity

O(N*M), where N is the number of rows and M is the number of columns.

In the recursion stack there will be at max N*M integers stored here, hence the space complexity will be O(N*M).

(100% EXP penalty)

Min Jumps

Console