Last Updated: 18 Mar, 2021
Minimum Cost to cross Grid
Moderate
Asked in companies
You are given a 2 - D grid having ‘N’ rows and ‘M’ columns. Each cell of the grid has an integer value written on it which denotes the cost it takes to pass through that cell. You are currently present at the Top-Left cell (0,0) and you want to reach the Bottom-Right cell (N - 1, M - 1). To do so, you start moving from the Top-Left cell and move through any of the adjacent cells until you reach the Bottom-Right cell. The total cost of the path will be the sum of the costs of all the cells that you have passed through in the path.
Given the cost of each cell in a 2 - D matrix 'MAT', your task is to find the minimum total cost that you need to spend to reach the Bottom-Right cell if you are starting from the Top-Left cell.
Note:
1) From any cell you can move UP, DOWN, LEFT, or RIGHT.
2) You cannot move out of the grid.
Input Format :
The first line of the input contains an integer 'T,’ denoting the number of test cases.
The first line of each test case contains two space-separated integers, 'N' and 'M', denoting the number of rows and columns in the grid respectively.
Each of the next 'N' lines contains 'M' space-separated integers denoting the cell values of the grid.
Output Format :
For each test case, print a single line containing a single integer denoting the minimum total cost that you need to spend to reach the Bottom-Right cell if you are starting from the Top-Left cell.
The output of each test case will be printed in a separate line.
Note:
You are not required to print the expected output. it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 10
1 <= N <= 200
1 <= M <= 200
1 <= MAT[i][j] <= 10 ^ 4
Where 'MAT[i][j]' denotes the element present at the 'i'th' row and the 'j'th' column of the matrix 'MAT'.
Time limit: 1 sec.
Approaches
The idea is to convert this problem as a graph problem. Each cell of the grid can be considered as a graph vertex and their costs can be considered as the weight of the vertices. We will add unweighted edges between all the pairs of adjacent cells. Using the above observations, the problem can be simplified to finding the shortest path between the Top-Left cell and Bottom-Right cell. This can be done efficiently with the help of the Dijkstra algorithm. Note that we do not need to explicitly build a graph, as we will be using the fact that for a particular cell, all edges from it exist with its adjacent cells only.
Steps:
- Let cost be a N*M 2-D matrix where cost[i][j] stores the minimum total cost to reach cell (i,j) starting from cell (0,0). Initialize all values of the matrix as INT_MAX.
- Let heap be a min-heap that will be used for implementing the Dijkstra algorithm. The heap stores the row and column of each cell, and it also stores the cost to reach that cell which is also used as the comparison operator to build the heap.
- Let deltaX be an array of 4 integers that stores the difference of the X-coordinates of the cell with its neighbours. Add the 4 integers -1, 1, 0 and 0 to the array deltaX.
- Let deltaY be an array of 4 integers that stores the difference of the Y-coordinates of the cell with its neighbours. Add the 4 integers 0, 0, 1 and -1 to the array deltaY.
- Add the cell (0,0) having cost MAT[0][0] to the heap, and set cost[0][0] as MAT[0][0].
- While the heap is non-empty, then
- Pop an element from the heap. Let the extracted cell be (x,y).
- Iterate from i = 0 to 3
- Let currX be x + deltaX and currY be y + deltaY, where (currX,currY) denotes the neighbour cell that is currently being considered.
- If the cell (currX,currY) lies inside the grid, then
- Let newCost denote the cost to reach the cell (currX,currY). Set newCost as cost[x][y] + MAT[currX][currY].
- If newCost is smaller than cost[currX][currY], then
- Set cost[currX][currY] as currCost
- Insert the cell (currX,currY) to the heap.;
- Return the value cost[N-1][M-1] as the cell (N-1,M-1) denotes the bottom-right cell.
Similar problems