Trong bài toán Mã đi tuần có một kĩ thuật là kĩ thuật hàng rào, để chặn không cho con Mã đi vượt khỏi bàn cờ? Em có nghe qua nhưng không tìm được tài liệu để đọc. Mong anh chị nào có tài liệu hay có thể giải thích cho em cũng được. Em xin cảm ơn
Kĩ thuật hàng rào trong bài toán Mã đi tuần
Chỉ là if thôi.
if (bước tiếp theo không chạy ra khỏi bàn cờ)
run(bước tiếp theo);
Không phải. Kĩ thuật sentinel dùng để loại bỏ một dãy điều kiện bằng cách thêm vào input.
1 Like
Anh nói rõ hơn tí được không anh?
1D thì ví dụ đơn giản là tìm một số x trong dãy. Có hai điều kiện dừng là tìm được và đã lặp qua hết. Ta sẽ loại bỏ điều kiện “lặp qua hết” bằng cách chèn x ngay sau phần tử cuối cùng, vậy điều kiện dừng chỉ còn một và lúc nào cũng “tìm được”, sau đó chỉ cần kiểm tra biến lặp (viết for(int i = …) sẽ không làm được bước này).
2D thì trong bài mã đi tuần, quân mã có thể di chuyển 2 ngang hoặc 2 dọc. Vậy viền mỗi cạnh phải rộng 2 ô và ta đánh dấu vào viền đó là “đã đi qua rồi”, vậy từ hai (biểu thức) điều kiện (“ngoài biên”) chỉ còn một là “chưa đi qua”.
Thế thì giống như bình thường thôi ạ?
run(ô hiện tại) {
if (ô tiếp theo chưa đi qua và không nằm ngoài bàn cờ) {
// code
run(ô tiếp theo)
}
}
Có nghĩa là bọc thêm quanh bàn cờ - giống hàng rào quanh nhà - các ô đã được đánh trước là visited.
Bàn cờ 3x3 có hàng rào là hình vuông cạnh 4 ô
1 Like
Kĩ thuật này giảm số biểu thức điều kiện 
(đỡ được 4 cái giờ còn 1 thôi) còn lại như cũ. Điều kiện bị loại bỏ đều là kiểu có ra ngoài biên hay không.
1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?