Grid Navigation and Pathfinding

Robots follow F, F2, L and R on a grid. We track where they stop, find the fewest moves through a maze and count shortest routes.

Key ideas

Cells are (column, row) with (1, 1) at the bottom left; F moves one cell, F2 two cells, L and R turn 90° in place.
Keep a record of the cell AND the facing after every command.
Fewest moves in a maze: number the squares by their distance from the start, ring by ring.
To count shortest routes in a maze, each square gets the sum of the counts of the squares just before it.
On a street grid moving right or up, each corner gets the corner to its left plus the corner below; a closed corner gets 0.
Fewest steps back to the start is the East–West difference plus the North–South difference.

Remember

Right turns from North	North → East → South → West
Facing and moving	North: row + 1; East: column + 1; South: row − 1; West: column − 1
Routes on a 3 × 2 street grid	10
Steps back	5 East, 2 North, 8 West → 3 + 2 = 5 steps

Watch out

Forgetting that F2 moves two cells.
Counting routes that pass through a closed corner.
Adding every step walked instead of the net East–West and North–South distances.

Worked example

(a) On a street grid you walk from corner (0, 0) to corner (5, 3), moving only right (east) or up (north), one block at a time. The corner (4, 1) is closed for repairs. How many different shortest routes are there?
(b) On a grid of streets, a delivery robot goes 3 steps South, then 1 step South, then 8 steps East, then 6 steps North. It can only move North, South, East or West. What is the fewest number of steps to get back to the start?

Working: (a) write at each corner the number of ways to reach it: the corner to its left plus the corner below; the closed corner gets 0; (b) it ends 8 East and 2 North of the start

Answer: (a) 41; (b) 10