Last Updated: 25 Dec, 2020
Min Jumps
Easy
Asked in companies
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.
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
Approaches
- 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.
- Since the complexity of the recursive approach is exponential, we will have to optimize it using dynamic programming. We can apply dynamic programing because,
- Let the 2D array be DP[][] where DP[X][Y] will store the minimum cost of reaching till the cell (X, Y). Initialize each of the DP[X][Y] cells with INT_MAX.
- Now at every step we have 3 options, to go right or bottom or bottom right. In other words , when we are at a cell ( i, j ), we can say that we have reached here from 3 possible(and valid) cells ( i - 1, j), (i,j-1) and ( i - 1, j - 1) So we can find the cost by visiting each cell and find the minimum cost.
- Let leftCost denote the cost of coming from the left of the adjacent cell then LEFTCOST = DP[X][Y - 1] + abs(ARR[X][Y] - ARR[X][Y - 1]).
- Similarly we can find topCost and diagonalCost for the cells ( X + 1, Y) and ( X + 1, Y + 1) respectively.
- After finding these values, we can take the minimum of the three and store the minimum of them in DP[X][Y].
- Finally our answer will be stored in the cell DP[N - 1][M - 1].