Tìm một đường đi bằng quay lui

```python def solveMaze(maze, m, n, x, y, sol, goals=None): if not (0 <= x < n and 0 <= y < m): return False if maze[y][x] != 0 or sol[y][x] == 1: return False if goals is None: goals = {(n - 1, m - 1)} sol[y][x] = 1 if (x, y) in goals: return True for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]: if solveMaze(maze, m, n, x + dx, y + dy, sol, goals): return True sol[y][x] = 0 return False ``` Mỗi lời gọi xét một ô. Trước hết kiểm biên, tường và việc ô đã nằm trong đường hiện tại; sau đó mới đánh dấu sol[y][x]=1. Nếu gặp đích thì trả True. Nếu chưa tới đích, thử phải, xuống, trái, lên theo thứ tự các cặp (dx,dy). Một lời gọi con thành công làm các mức trước trả True ngay, giữ nguyên vết đường. Chỉ khi cả bốn hướng thất bại mới đặt lại 0 và trả False. Ô bị bỏ khỏi nhánh này vẫn có thể được thử trong một nhánh khác. Không đánh dấu sẽ dễ đi vòng lại các ô cũ.

Đặt mã và tệp mẫu trong cùng thư mục, rồi chạy: ```text python3 g11-cs-me-cung.py g11-cs-me-cung.inp --output maze.out ``` Cần nhận kích thước 4 hàng 5 cột, xuất phát (0,0), cùng ma trận vết trên màn hình và trong maze.out. Kiểm đầu/đích có dấu 1, mọi ô trên đường ứng với maze bằng 0 và mỗi bước chỉ đổi hàng hoặc cột một đơn vị. Tệp kết quả được ghi bằng chế độ w, thay nội dung cũ. Nếu không có đường, bản thực hành thông báo và ghi tệp rỗng để tránh đọc nhầm kết quả lượt trước. Tệp kết quả phải khác tệp đầu vào. Bản chạy một đường nhận tối đa 60 ô để giữ việc thực hành trong lưới nhỏ.