Hướng dẫn giải của Đường Đi Hamilton

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

Lời giải: Gặm Cỏ

Hướng tiếp cận

Đếm số đường đi Hamilton trên lưới $5 \times 5$ từ ô $(1, 1)$ đến ô $(5, 5)$ bằng thuật toán quay lui (backtracking/DFS). Lưới nhỏ nên brute-force hoàn toàn khả thi.

Nhận xét quan trọng

Lưới chỉ có $5 \times 5 = 25$ ô. Dù số đường đi lý thuyết lớn, việc cắt tỉa sớm (pruning) làm cho DFS chạy rất nhanh.
Khi có $K$ ô bị chặn, tổng số ô cần thăm là $25 - K$ (luôn bao gồm $(1, 1)$ và $(5, 5)$ , vì $K \leq 22$ và $K$ chẵn).
Cần đánh dấu ô đã thăm và bỏ qua ô bị chặn.

Thuật toán

Đọc $K$ ô bị chặn, đánh dấu vào mảng blocked[5][5].
Đếm tổng số ô không bị chặn target = 25 - K.
DFS từ (1,1) với bộ đếm số ô đã thăm:
- Nếu đang ở $(5, 5)$ và đã thăm đúng target ô: tăng đáp án lên 1, quay lui.
- Thử 4 hướng (lên/xuống/trái/phải): nếu ô hợp lệ, chưa thăm, không bị chặn thì đi vào, đệ quy tiếp, rồi bỏ đánh dấu.
In kết quả.

Độ phức tạp

Thời gian: $O (4^{25})$ trong trường hợp xấu nhất, nhưng pruning cắt tỉa mạnh. Thực tế rất nhanh với lưới $5 \times 5$ .
Bộ nhớ: $O (25)$ (chiều sâu đệ quy tối đa)

Bình luận

Không có bình luận tại thời điểm này.