Problem Description

You are tasked with implementing a maze pathfinding solution in C++. The maze is represented as an m x n grid.

• . denotes an open cell.
• # denotes a wall.
• S denotes the start position.
• T denotes the target position.

Movement is restricted to up, down, left, or right, with each move incurring a cost of 1.

Requirements

1. Algorithm: Utilize the A* algorithm to find a shortest path from S to T.
2. Output:
   • Return the minimum distance (total cost) of the shortest path.
   • Return one valid shortest path as a list of coordinates.
   • If no path exists, the solution should report failure.
3. Implementation Details:
   • Employ an admissible heuristic.
   • Maintain necessary data structures to reconstruct the path.
   • Ensure the algorithm avoids revisiting states unnecessarily.
   • Provide an analysis of the time and space complexity of your solution.