Câu hỏi 8
Trong một trò chơi máy tính, mê cung được biểu diễn bằng bảng ô vuông. Ô xám là bẫy, ô trắng là ô an toàn. Jay đang đứng trên ô trắng được đánh dấu “J”. Jay có thể nhảy từ ô trắng này sang ô trắng khác, nhưng chỉ theo hàng ngang hoặc cột dọc và xa không quá 3 ô. Jay có thể nhảy qua một dãy ô xám, nhưng không được nhảy qua ô trắng khác và không được đáp xuống ô xám.
Ví dụ ở hình dưới, từ “J”, Jay có thể nhảy sang phải ba ô hoặc xuống dưới hai ô, nhưng không được nhảy sang trái bốn ô hay xuống dưới ba ô. Muốn đến ô trắng khác nữa phải thực hiện thêm các lần nhảy.
Trong mê cung sau, Jay xuất phát ở “J”. Cần ít nhất bao nhiêu lần nhảy để bảo đảm bất kỳ ô trắng nào khác cũng có thể đến được từ vị trí xuất phát này?
Ví dụ ở hình dưới, từ “J”, Jay có thể nhảy sang phải ba ô hoặc xuống dưới hai ô, nhưng không được nhảy sang trái bốn ô hay xuống dưới ba ô. Muốn đến ô trắng khác nữa phải thực hiện thêm các lần nhảy.
Trong mê cung sau, Jay xuất phát ở “J”. Cần ít nhất bao nhiêu lần nhảy để bảo đảm bất kỳ ô trắng nào khác cũng có thể đến được từ vị trí xuất phát này?