Shortest Path in a Grid with Obstacle Removal

BFS shortest path from a start cell to an end cell in a grid with blocked cells, with a follow-up that lets you convert blocked cells to open ones. Requirements Find the shortest path from a start cell to an end cell in a grid where some cells are blocked. Movement is between adjacent cells; return the length of the shortest path, or report that none exists. Base version: a standard breadth-first search over open cells. Follow-up: you may convert blocked cells into open cells. Recompute the shortest path under that relaxation — still BFS, now over an expanded state space. Notes The base problem is plain grid BFS from source to target. The follow-up adds the ability to clear obstacles; the canonical handling is to make the BFS state (row, col, obstacles_cleared_so_far) so the same cell can be revisited with a different remaining budget. Both parts were left deliberately open-ended — clarify the exact rules (4- vs 8-directional movement, how many cells may be converted, whether conversions are free or budgeted) before coding.