Kĩ thuật hàng rào trong bài toán Mã đi tuần

kĩ thuật hàng rào, để chặn không cho con Mã đi vượt khỏi bàn cờ

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.

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 ô

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.

Bài toán mã chạy rông

or http://plnkr.co/edit/wjTZ6P?p=preview