Implement a program that finds the shortest path in an unweighted 2D grid using Breadth-First Search (BFS). Given a grid with obstacles and start/end positions, return the minimum number of steps needed to reach the destination.
solve function signature must remain unchanged
Input:
grid (4x4) = [
[0, 0, 0, 0],
[1, 1, 0, 1],
[0, 0, 0, 0],
[0, 1, 1, 0]
]
start_row = 0, start_col = 0
end_row = 3, end_col = 3
Output: 6
Explanation: One possible shortest path:
(0,0) → (0,1) → (0,2) → (1,2) → (2,2) → (2,3) → (3,3)
Input:
grid (3x3) = [
[0, 1, 0],
[1, 1, 1],
[0, 0, 0]
]
start_row = 0, start_col = 0
end_row = 0, end_col = 2
Output: -1
Explanation: No path exists due to obstacles completely blocking the way.
rows, cols ≤ 1000cols = 500, rows = 500