Minimum Cost to Destination

Hard
0/120
Average time to solve is 41m
profile
Contributed by
12 upvotes
Asked in companies
AmazonOYOBarclays

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
4 4
1 0 1 0
1 1 0 1
0 0 0 1
1 1 0 1
3 3
Sample Output 1 :
-1
 Explanation to Sample Input 1 :
It is impossible to reach (3, 3) from (0, 0), so Output is -1.
Sample Input 2 :
5 5
1 0 1 0 0
1 0 1 1 1
1 1 1 0 1
0 0 0 0 1
1 1 1 1 1
3 4
Sample Output 2 :
5
 Explanation to Sample Input 2 :
The optimal path to reach (3, 4) from (0,0) is :
(0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2) -> (1, 2) -> (1, 3) -> (1, 4) -> (2, 4) -> (3, 4)
So the cost is : 1 + 1 + 0 + 0 + 1 + 0 + 0 + 1 + 1 = 5
Hint

Try to explore all the possibilities, i.e. going in all four directions and find the minimum cost.

Approaches (3)
Backtracking

Maintain a visited array and try to explore all the possibilities with the help of backtracking.

  1. Start with (0, 0) and mark it as visited and try to move in all 4 directions.
  2. Say at any point we are at (i, j) then the cost of reaching (x,y) will be the minimum of these four cases.
    1. Option 1 -  Left: cost of reaching from (i, j-1)
    2. Option 2 - Right: cost of reaching from (i, j+1)
    3. Option 3 - Up: 1 + cost of reaching from (i-1, j)
    4. Option 4 - Down: 1 +  cost of reaching from (i+1, j)
  3. Base case will be when (i,j) = (x,y), then return 0.
  4. If we didn’t reach the Destination (x,y) then return -1.
  5. Also, take care of going out of bounds and cells which are blocked.
Time Complexity

O(4^K), where K = N*M and N is no. of rows and M is no. of columns in the matrix.

 

There are 4 possibilities as each cell and there are total K cell so 4^K is Overall time Complexity.

Space Complexity

O(K), where K = N*M and N is no. of rows and M is no. of columns in the matrix.

 

We are using a visited matrix of size K also our recursive call stack can also have maximum depth as K. So Overall Space Complexity is O(K).

Code Solution
(100% EXP penalty)
Minimum Cost to Destination
Full screen
Console