Last Updated: 16 Jul, 2020
Minimum Cost to Destination
Hard
Asked in companies
You have been given an N*M matrix where there are 'N' rows and 'M' columns filled with '0s' and '1s'.
'1' means you can use the cell, and '0' means the cell is blocked. You can move in the 4 following directions from a particular position (i, j):
1. Left - (i, j-1)
2. Right - (i, j+1)
3. Up - (i-1, j)
4. Down - (i+1, j)
Now, for moving in the up and down directions, it costs you $1, and moving to the left and right directions are free of cost.
You have to calculate the minimum cost to reach (X, Y) from (0, 0) where 'X' is the row number and 'Y' is the column number of the destination cell. If it is impossible to reach the destination, print -1.
Input format :
The first line of input contains two integer values, 'N' and 'M', separated by a single space. They represent the 'rows' and 'columns' respectively, for the two-dimensional array/list.
The second line onwards, the next 'N' lines or rows represent the i-th row values.
Each of the ith row constitutes 'M' column values separated by a single space.
The next and the final line contains two single space separated Integers 'X' and 'Y' where 'X' is the row number and 'Y' is the column number of the destination cell.
Output format :
Print the minimum cost required to reach the destination (X, Y) from (0, 0).
If it is impossible to reach the destination, print -1.
Note :
1. You are not required to print the output explicitly, it has already been taken care of. Just implement the given function.
2. 'X' and 'Y' are 0-based indexing.
3. matrix[0][0] will always be 1.
Constraints :
1 <= N <= 10^3
1 <= M <= 10^3
0 <= matrix[i][j] <= 1
0 <= X < N
0 <= Y < M
where 'N' represents the number of rows, 'M' represents the number of columns, 'matrix[i][j]' represents the elements of the matrix, and 'X' and 'Y' represents the coordinates of the destination point.
Time Limit: 1 sec.
Approaches
Maintain a visited array and try to explore all the possibilities with the help of backtracking.
- Start with (0, 0) and mark it as visited and try to move in all 4 directions.
- Say at any point we are at (i, j) then the cost of reaching (x,y) will be the minimum of these four cases.
- Option 1 - Left: cost of reaching from (i, j-1)
- Option 2 - Right: cost of reaching from (i, j+1)
- Option 3 - Up: 1 + cost of reaching from (i-1, j)
- Option 4 - Down: 1 + cost of reaching from (i+1, j)
- Base case will be when (i,j) = (x,y), then return 0.
- If we didn’t reach the Destination (x,y) then return -1.
- Also, take care of going out of bounds and cells which are blocked.
We will use Breadth-First Search with Priority Queue to solve the problem (Similar to Dijkstra’s Algorithm).
To make our operations easy, we create a new class called Cell, which stores the cost to reach that cell, the x coordinate and y coordinate of a particular cell, in that order.
- We will maintain a Min Heap (Priority Queue) of Cell(cost, i, j) where (i,j) is cell no. and the cost is the cost of reaching (i,j) from (0,0).
- Min Heap will be ordered according to cost. So that we can get a cell with minimum cost on the top of the priority queue.
- Create a minCost Matrix and initialize it with the maximum value (INT_MAX)
- Start with pushing Cell(0, 0, 0) and updating minCost[0][0] = 0, as cost of reaching cell (0,0) is 0.
- Iterate till we reach the destination or our priority queue is empty.
- In each iteration, we pop the top Cell having the minimum cost and try to update the cost of all four neighbours:
- Left - (i, j-1) : curCost
- Right - (i, j+1) : curCost
- Up - (i-1, j): curCost + 1
- Down - (i+1, j): curCost + 1
- If the updating value is less than prior value then we update the minCost Matrix and push the cell in our Priority Queue. (If the new cost is greater than the prior cost, we don't push it as we already have a more optimal cost for the cell.)
- Finally if minCost[x][y] = maximum value (INT_MAX) then we can’t reach Destination (x,y) so return -1 else return the minCost[x][y].
- Also, take care of going out of bounds and cells which are blocked.
We will use Breadth-First Search with deque to solve the problem (This technique is called 0-1 BFS and it is used when we can only have 0 or 1 as our cost from one node to another)
To make our operations easy, we create a new class called Cell, which stores the cost to reach that cell, the x coordinate and y coordinate of a particular cell, in that order.
- We will maintain a deque of Cell(cost, i, j) where (i,j) is cell no. and the cost is the cost of reaching (i,j) from (0,0).
- This deque will always have a cell with minimum cost in the front. Also, it will always contain cells having at max two costs say, C1 and (C1 + 1). C1 cost cells in the front and (C1 + 1) cost cells in the back.
- Create a minCost Matrix and initialize it with the maximum value (INT_MAX)
- Start with pushing Cell(0, 0, 0) and updating minCost[0][0] = 0, as cost of reaching cell (0,0) is 0.
- Iterate till we reach the destination or our deque is empty.
- In each iteration, we pop the front Cell having the minimum cost and try to update the cost of all four neighbours:
- Left - (i, j-1) : curCost
- Right - (i, j+1) : curCost
- Up - (i-1, j): curCost + 1
- Down - (i+1, j): curCost + 1
- If the updating value is less than prior value then we update the minCost Matrix and push the cell in our deque. (If the new cost is greater than the prior cost, we don't push it as we already have a more optimal cost for the cell.)
- For Left and Right direction, we will push the cell in the front as it will have same cost as of popped cell.
- For Up and Down, we will push the cell in the back as it will have cost 1 greater than the cost of popped cell.
- These two operations will ensure the above-mentioned properties of our deque.
- Finally if minCost[x][y] = maximum value (INT_MAX) then we can’t reach Destination (x,y) so return -1 else return the minCost[x][y].
- Also, take care of going out of bounds and cells which are blocked.