Minimum Cost to Destination
You are given an NxM matrix consisting of '0's and '1's. A '1' signifies that the cell is accessible, whereas a '0' indicates that the cell is blocked. Your task is to compute the minimum cost required to travel from the starting point (0, 0) to a specified destination (X, Y).
You can move in the following four directions from any given cell (i, j):
1. Left - (i, j-1) 2. Right - (i, j+1) 3. Up - (i-1, j) 4. Down - (i+1, j)
Traversing in the 'Up' and 'Down' directions incurs a cost of 1. Movements to the 'Left' and 'Right' are free of cost. If it is impossible to reach (X, Y), return -1.
Input:
The first line contains two integers 'N' and 'M', representing the number of rows and columns of the matrix, respectively. The next N lines contain M integers each, representing the row values of the matrix. The final line consists of two integers, 'X' and 'Y', denoting the destination coordinates.
Output:
Print the minimum cost to reach (X, Y) from (0, 0). If the destination is unreachable, print -1.
Example:
Input:
3 3 1 0 1 1 1 0 0 1 1 2 2
Output:
2
Constraints:
- 1 <= N <= 10^3
- 1 <= M <= 10^3
- 0 <= matrix[i][j] <= 1
- 0 <= X < N
- 0 <= Y < M
Note:
- The starting point matrix[0][0] will always be 1.
- 'X' and 'Y' are 0-based indices.
- You do not need to print the output, implement the function that computes the result.
Find the minimum cost to reach a destination in a matrix with specified rules.
Use Breadth First Search (BFS) algorithm to explore all possible paths from the starting point to the destination.
Keep tra...read more
Top Travclan Technology India Technical Trainee interview questions & answers
Popular interview questions of Technical Trainee
Reviews
Interviews
Salaries
Users/Month