A* Pathfinding on a Grid

A* finds shortest paths faster than Dijkstra by using a heuristic: an estimate of the remaining distance that never overestimates it.

Implement a_star(grid, start, goal):

• grid is a list of strings, where "." is open and "#" is a wall. Positions are (row, col).
• Moves go up, down, left or right, each costing 1. Use the Manhattan distance as the heuristic.
• Return the shortest path as a list of positions from start to goal inclusive, or None if unreachable (including when start or goal is a wall).
• Several shortest paths may exist. Return any one, but it must be valid and shortest.

Also implement path_length(path), the number of moves (len(path) - 1).