Implement A* Maze Search
Company: Qualcomm
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement maze pathfinding in C++. You are given an `m x n` grid where `'.'` is an open cell, `'#'` is a wall, `S` is the start, and `T` is the target. You may move up, down, left, or right, and each move has cost `1`.
Use the A* algorithm to find a shortest path from `S` to `T`. Return the minimum distance and one valid shortest path as a list of coordinates. If no path exists, report failure.
Your solution should:
- use an admissible heuristic,
- maintain the data needed to reconstruct the path,
- avoid revisiting states unnecessarily,
- and analyze time and space complexity.
Overview: This question evaluates proficiency in informed search algorithms, heuristic design (admissibility), grid-based graph traversal, path reconstruction, and time/space complexity analysis.