Lesson 5-1 · Finding a Way Around — Knowledge ChecksAnswer key
Why can't the Manhattan algorithm route around a blocked intersection?
Manhattan always follows the same L-shaped route. It never checks whether an intersection is blocked, so it can't detour.
With (1,0) blocked, the shortest path from (0,0) to (2,0) is 4 steps, but the Manhattan distance is 2. What does that tell you?
Manhattan distance is the shortest path with NO obstacles. Blocked intersections can force a longer detour, so it becomes a lower bound.
An intersection already has a 2 on it. Later, while looking around an intersection with a 3, you find it's a neighbor. What do you write on it?
An intersection is numbered once, the first time it's reached. Because the wave reaches everything at one distance before anything further out, that first number is already the smallest possible.
The start has just been given a 5. Could a shorter way from the start to the destination still turn up?
The wave reaches everything closer first, so the first number written on the start can't be beaten.