Walk the grid

A* expands the cell with the smallest cost-so-far plus a heuristic. On a grid of orthogonal steps, Manhattan distance to the goal never overestimates, so the first time the goal is expanded the path is shortest.

Moves are up, down, left, and right. S is the top-left cell, G is the bottom-right, and the center cell is blocked. Enter the number of steps in a shortest path.