Lee (Grid BFS shortest path)
Self‑contained grid pathfinding with the Lee algorithm (breadth‑first search on a 4‑neighborhood).
What this is?
The Lee algorithm finds the shortest path in a grid with uniform step cost. It’s a classic breadth‑first search: we expand from the start, layer by layer, until we reach the goal. Then we backtrack by following decreasing distance values to reconstruct a shortest path. Works with walls (blocked cells) and 4‑neighborhood moves.
Text
Paste or copy your grid here. Use # for walls, . for empty, S start, G goal.
Answer
Reason why
On grids with unit weights, BFS explores in concentric “rings”. The first time it dequeues the goal, the discovered distance is optimal. The backtracking step simply walks to any neighbor with distance −1 until it reaches the start. Obstacles are simply never enqueued.