Shortest Path in a Binary Grid
Imagine a robot navigating a warehouse represented by a grid. Some cells are clear, others are blocked. The robot needs to find the quickest way from its starting point to a delivery destination. This problem challenges you to find the minimum number of steps required to reach a target cell from a start cell in a grid, avoiding obstacles. This is a fundamental problem in pathfinding and graph theory, crucial for applications like game AI, logistics, and network routing.
Implement a function that calculates the minimum number of steps to reach a target cell from a starting cell in a given binary grid.
1).-1.grid: A 2D array of integers (number[][]) representing the maze. 0 indicates an an open path, 1 indicates an obstacle.start: An array of two integers [row, col] representing the starting cell coordinates.target: An array of two integers [row, col] representing the target cell coordinates.-1 if the target is unreachable or if start or target are obstacles.start and target coordinates will always be within the grid boundaries.start cell itself is an obstacle (1), or the target cell is an obstacle (1), the target is considered unreachable, and the function should return -1.start and target are the same cell and it's not an obstacle, the path length is 0.Examples
Example 1
Input:
grid = [[0,0,0],[0,1,0],[0,0,0]], start = [0,0], target = [2,2]
Output:
4
Note:
Path: (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2). Total 4 steps.
Example 2
Input:
grid = [[0,1,0],[0,0,0],[0,1,0]], start = [0,0], target = [2,0]
Output:
6
Note:
Path: (0,0) -> (1,0) -> (1,1) -> (1,2) -> (2,2) -> (2,1) -> (2,0). Total 6 steps.
Example 3
Input:
grid = [[0,1,0],[0,1,0],[0,1,0]], start = [0,0], target = [0,2]
Output:
-1
Note:
The target cell [0,2] is unreachable from [0,0] due to obstacles.
Constraints
1 <= grid.length, grid[0].length <= 200 (Grid dimensions will be at most 200x200)grid[i][j] is 0 or 1.start and target will be valid coordinates within the grid.Loading editor...