Where it runs
1. The problem
You have a grid map. Some cells are open, and you can walk on them. The other cells are walls. You stand on a start cell and need one particular goal cell. You can move up, down, left and right. You want the fewest steps to the goal.
Grid BFS (step 90) and Dijkstra (step 97) both solve this, but they spread out blindly in every direction. Say the goal is far to the east. They still push west, north and south just as hard and check thousands of cells that will never be needed. On a big map that is slow.
A* cuts that extra work. It is Dijkstra with one addition: for each cell it estimates how far the goal still is. That estimate steers the search toward the goal. So A* opens far fewer cells and gets the same shortest answer.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedOn LeetCode
Shortest path on a grid or a puzzle board when you know where the goal is. LeetCode accepts plain BFS on these, and A* with a distance guess that never overestimates gets the same answer while opening fewer cells.
Moves go in 8 directions here, so swap the lesson's Manhattan guess for the larger of the row gap and the column gap.
Each board state is a node, and the sum of each tile's Manhattan distance to its home never overestimates the moves left.
You walk from tree to tree in height order, and each walk is one A* search on the forest grid.