Trong bài toán tìm kiếm đường đi (Pathfinding) trên ma trận, tại sao việc sử dụng mảng đánh dấu 'visited' lại quan trọng và làm sao để hoàn tác (backtrack) trạng thái này một cách chính xác?

Question

Accepted Answer

Tầm quan trọng của mảng visited
Trong Backtracking, chúng ta cần đảm bảo không sử dụng lại một ô đã đi trong cùng một hành trình để tránh rơi vào vòng lặp vô tận (Infinite loop).
Cơ chế hoàn tác
Sau khi gọi đệ quy cho các hướng đi tiếp theo, ta phải đặt lại giá trị của ô đó về trạng thái ban đầu (thường là false hoặc ký tự gốc) để các nhánh khác có thể sử dụng ô này.
Ví dụ minh họa
visited[r][c] = true;
// Gọi đệ quy cho 4 hướng
const found = dfs(r + 1, c) || dfs(r - 1, c) ...;
// Hoàn tác (Backtrack)
visited[r][c] = false;
return found;
Lưu ý thực chiến
Nếu quên bước hoàn tác, thuật toán sẽ chỉ tìm được một đường đi duy nhất hoặc không tìm thấy đường đi nào cả do các ô đã bị đánh dấu vĩnh viễn.

Trong bài toán tìm kiếm đường đi (Pathfinding) trên ma trận, tại sao việc sử dụng mảng đánh dấu 'visited' lại quan trọng và làm sao để hoàn tác (backtrack) trạng thái này một cách chính xác?

Tầm quan trọng của mảng visited

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi backtracking liên quan cùng chủ đề