Last Updated: 10 Jan, 2021
Minimum Cost to Make at Least One Valid Path in a Grid
Moderate
Asked in company
You have been given a grid of ‘N’ * ‘M’ dimension. Each cell of the grid has an integer sign pointing to the next cell which you can visit from the current cell. There can be four possible value at ‘GRID[ i ][ j ]’ :
1 - Which means you can go from (i, j)-th cell to the (i, j+1)-th cell.
2 - Which means you can go from (i, j)-th cell to the (i, j-1)-th cell.
3 - Which means you can go from (i, j)-th cell to the (i+1, j)-th cell.
4 - Which means you can go from (i, j)-th cell to the (i-1, j)-th cell.
Now, you start travelling from the (0, 0)-th cell and want to visit (N-1, M-1)-th cell following a valid path. A valid path in the grid is a path which starts from the upper left cell (0,0) and ends at the bottom-right cell (M - 1, N - 1) following the signs on the grid. The valid path doesn't have to be the shortest. You are allowed to change the sign of any cell only once as per your wish by incurring a cost of 1. So you are supposed to find the minimum cost to make at least one valid path in a grid.
Input Format :
The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.
The first input line of each test case contains two 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, return the minimum cost to make at least one valid path in the grid.
Print the output of each test case 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 <= 50
1 <= N <= 100
1 <= M <= 100
Time limit: 1 sec
Approaches
The basic idea of this approach is to model this problem as a graph problem. Let us create a directed weighted graph with cells of the given grid as vertices. There will be an edge of weight 0 if we can move from (i, j)-th cell to neighbouring cells (i, j+1), (i, j-1), (i+1, j) following the sign of (i, j)-th cell, otherwise the weight of the edge will be 1.
The figure below shows the graph constructed for the first test case of sample test case 1. Edges of weight 0 are denoted in red colour and whereas black edges are of weight 1.
We can observe that the problem finally boils down to finding the single source shortest path in a directed weighted graph. We can use the Dijkstra algorithm to do this task. You can refer to this tutorial of cp-algorithms for a more detailed explanation of the Dijkstra algorithm. https://cp-algorithms.com/graph/dijkstra_sparse.html
We will be using a min-heap based implementation of the Dijkstra algorithm. Now consider the following steps :
- Let ‘DIST[ i ][ j ]’ a matrix of ‘N’ * ‘M’ dimension which stores the shortest path length from (0, 0)-th cell to (i, j)-th cell. We will initialise this matrix with a very large integer.
- Now, create a min-heap of <int, <int, int>> which stores the path length from (0, 0)-th cell to (i, j)-th cell.
- Next, push the starting cell to the min-heap and update the “DIST” for this cell. ‘DIST[0][0]’ = 0
- Now, start iterating while the min-heap is not empty.
- Extract the cell with the minimum distance. Let say it is ('X', ‘Y’)-th cell.
- Iterate through the neighbouring cells i.e. ('X', ‘Y’-1), ('X', ‘Y’+1), ('X'-1, ‘Y’) and ('X'+1, ‘Y’). Check if they are valid (lies inside the grid), then
- Check if we can move from ('X', ‘Y’) to next cell using the sign at 'GRID['X']['Y']', then update distance of next cell as the same as the distance of ('X', ‘Y’). Because the edge weight will be zero in this case.
- Otherwise, we update the distance of the next cell by ‘DIST['X']['Y']’ + 1. Because the edge weight will be 1 in this case.
- And push the updated distance of the next cell into the min-heap.
- We can get the shortest path length from ‘DIST['N'-1]['M'-1]' which will be the minimum cost to make at least one valid path in the given grid.