304. Shortest Distance in a Binary Maze
Given an n x m matrix grid where each cell contains either 0 or 1, determine the shortest distance between a source cell and a destination cell. You can move to an adjacent cell (up, down, left, or right) if that adjacent cell has a value of 1. The path can only be created out of cells containing 1. If the destination cell is not reachable from the source cell, return -1.
Example 1:
Input: grid = [[1, 1, 1, 1],[1, 1, 0, 1],[1, 1, 1, 1],[1, 1, 0, 0],[1, 0, 0, 1]], source = [0, 1], destination = [2, 2]
Output: 3
Explanation: The shortest path from (0, 1) to (2, 2) is:
Move down to (1, 1)
Move down to (2, 1)
Move right to (2, 2)
Thus, the shortest distance is 3
Example 2:
Input: grid = [[1, 1, 1, 1, 1],[1, 1, 1, 1, 1],[1, 1, 1, 1, 0],[1, 0, 1, 0, 1]], source = [0, 0], destination = [3, 4]
Output: -1
Explanation:
Since, there is no path possible between the source cell and the destination cell, hence we return -1.
Now Your Turn!
Pick the correct output for the given inputInput: grid = [[1, 0, 1],[1, 1, 0],[1, 1, 1]], source = [0, 0], destination = [2, 2]
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 1 ≤ n, m ≤ 500
- grid[i][j] == 0 or grid[i][j] == 1
- The source and destination cells are always inside the given matrix.
- The source and destination cells are always traversable, i.e., grid[source.first][source.second] = 1 and grid[destination.first][destination.second] = 1.