Thuật toán tìm kiếm A* (A-Star) trên lưới tọa độ với Heuristic Manhattan

Mục tiêu kiến thức

• Triển khai thuật toán tìm đường A* (A-Star Search).
• Kết hợp hàm chi phí thực tế g(n) và hàm đánh giá heuristic h(n) với f(n) = g(n) + h(n).
• Sử dụng hàm Heuristic khoảng cách Manhattan |r₁ - r₂| + |c₁ - c₂| cho di chuyển 4 hướng (Lên, Xuống, Trái, Phải).

Mô tả bài toán

Cho một mê cung dạng ma trận grid kích thước R × C, trong đó ô có giá trị 0 là đường đi tự do và 1 là vật cản không thể đi vào.

Viết hàm a_star_grid_path(grid: list[list[int]], start: tuple[int, int], goal: tuple[int, int]) -> tuple[int, list[tuple[int, int]] | None]:

• start và goal là tọa độ (row, col).
• Nếu start hoặc goal nằm ngoài mê cung hoặc nằm trúng ô vật cản (grid[r][c] == 1), raise ValueError("Toa do start hoac goal khong hop le").
• Di chuyển theo 4 hướng chính, mỗi bước đi tốn chi phí 1.
• Trả về (min_steps, path):
• min_steps: số bước đi ngắn nhất từ start đến goal. Nếu start == goal, min_steps = 0 và path = [start].
• path: danh sách các tọa độ đi từ start đến goal.
• Nếu không tồn tại đường đi, trả về (-1, None).

Ràng buộc

• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào tuân thủ đúng kiểu dữ liệu và miền giá trị được mô tả.