Skip to main content
Module 5 · Pathfinding Around Obstacles

Lesson 5-1 · Finding a Way Around — Knowledge ChecksAnswer key

Correct answers are marked and the explanation follows each question.

  1. Why can't the Manhattan algorithm route around a blocked intersection?

    1. A.It runs too slowly
    2. B.It only knows one fixed strategy (across, then up or down) and has no concept of obstacles✓
    3. C.It can, if you turn it off and on again
    4. D.The robot has no wheels

    Manhattan always follows the same L-shaped route. It never checks whether an intersection is blocked, so it can't detour.

  2. 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?

    1. A.The Manhattan distance is wrong
    2. B.With obstacles, the real shortest path can be longer than the Manhattan distance✓
    3. C.Obstacles always add exactly 2 steps
    4. D.The destination is unreachable

    Manhattan distance is the shortest path with NO obstacles. Blocked intersections can force a longer detour, so it becomes a lower bound.

  3. 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?

    1. A.Nothing — it keeps its 2✓
    2. B.4, because 3 + 1
    3. C.3, the smaller of 3 and 4
    4. D.Cross out the 2 and write 4

    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.

  4. The start has just been given a 5. Could a shorter way from the start to the destination still turn up?

    1. A.No: every intersection 4 or fewer steps from the destination is already numbered, so 5 is the shortest✓
    2. B.Yes: finish the whole grid, then look for a smaller number on the start
    3. C.Yes: a path that heads straight toward the destination might be shorter
    4. D.It depends on how many intersections are blocked

    The wave reaches everything closer first, so the first number written on the start can't be beaten.