Minimum Cost to Make at Least One Valid Path in a Grid

Moderate
0/80
Average time to solve is 20m
4 upvotes
Asked in company
Amazon

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3 3
1 1 1
2 2 2
3 3 3
2 2
1 3
3 4
Sample output 1 :
2
0
Explanation of Sample output 1 :
For the first test case, you can change the sign of (0, 2)-th cell to 3 and (1, 2)-th cell to 3 after incurring the cost of 2. Then, you can follow the path (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (2, 2). So, the total cost is 2.

For the second test case, you can follow the path (0, 0) -> (0, 1) -> (1, 1) without changing the sign of any cell. So, the minimum cost will be 0.
Sample Input 2 :
2
2 2
1 2
4 3
1 1
5
Sample output 2 :
1
0
Explanation of Sample output 2 :
For the first test case, you can change the sign of (0, 1)-th cell to 3 after incurring the cost of 1. Then, you can follow the path (0, 0) -> (0, 1) -> (1, 1). So, the total cost will be 1.

For the second test case, starting cell and destination cell are the same which means we don’t need to make any changes. So, the minimum cost will be 0.
Hint

Can you think of converting this problem into a graph problem?

Approaches (1)
Shortest-path based approach

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 :

  1. 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.
  2. Now, create a min-heap of <int, <int, int>> which stores the path length from (0, 0)-th cell to (i, j)-th cell.
  3. Next, push the starting cell to the min-heap and update the “DIST” for this cell. ‘DIST[0][0]’ = 0
  4. 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.
  5. 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.
Time Complexity

O(N * M * log(N * M)), Where ‘N’ and ‘M’ denotes the number of rows and columns in the grid, respectively.

 

Since we are using the Dijkstra algorithm for finding the shortest path. And the complexity of this algorithm is O(|V| * log(|V|) + |E| * log(|V|)) where |V| is the number of vertices and |E| is the number of edges in the graph. In our construction, there are ('N' * ‘M’) vertices and at max ( 4 * ‘N’ * ‘M’) edges. So, the overall time complexity will be O('N' * ‘M’ * log('N' * ‘M’).

Space Complexity

O('N' * ‘M’), Where ‘N’ and ‘M’ denotes the number of rows and columns in the grid, respectively.

 

Since we are using “DIST” matrix of ‘N’ * ‘M’ dimension to store the distance and also we are using a min-heap which stores at max ‘N’ * 'M' elements. So, the overall space complexity will be O(N * M).

Code Solution
(100% EXP penalty)
Minimum Cost to Make at Least One Valid Path in a Grid
Full screen
Console