Chuyên đề Tin Học 11 KNTT Bài 16. Thực hành thiết kế thuật tóan theo kĩ thuật quay lui có đáp án

Để tìm ra các bước đi tiếp theo từ một vị trí trong mê cung khi áp dụng kĩ thuật duyệt quay lui, chúng ta cần kiểm tra các ô xung quanh ô hiện tại xem có thể đi được không. Nếu ô đó chưa được đi qua và là ô đích hoặc có thể đi đến ô đích từ ô đó thì chúng ta chọn ô đó làm ô tiếp theo và tiếp tục tìm đường đi từ ô đó. Nếu không có ô nào thỏa mãn điều kiện trên, chúng ta quay lại ô trước đó và tiếp tục kiểm tra các ô xung quanh ô đó. Quá trình này được lặp lại cho đến khi tìm được đường đi hoặc đã duyệt qua tất cả các ô mà không tìm được đường đi.

Để điểm bắt đầu tại m//2 và n//2, em chỉ cần thay đổi giá trị của biến x và y khi gọi hàm solveMaze. Thay vì truyền 0, 0 vào hàm solveMaze, em có thể truyền m//2, n//2

- Em cần sửa hàm writemaze in dữ liệu đầu ra và hàm soveMaze đặt giá trị tại các ô là 2 nếu ở đó là đường đi

- Hai hàm cần sửa như sau:

Để in ra tất cả các đường đi trong mê cung, bạn có thể sử dụng một hàm đệ quy để tìm và in ra tất cả các đường đi hợp lệ.

Để giải bài toán này, có thể sử dụng thuật toán quay lui (backtracking) để tìm tất cả các cách xếp Hậu một cách hợp lệ trên bàn cờ.

Em có thể tham khảo lời giải sau: