Đường đi của Robot
Đường đi của robot sẽ là đường viền của hình chữ nhật lớn bao quanh căn phòng (chu vi phòng) và các đường chia bên trong để tạo thành 8 phần bằng nhau.
Cụ thể, đường đi (đã lau) sẽ là:
- Đường viền ngoài của căn phòng (thực hiện yêu cầu "đi quanh được toàn bộ mép tường").
- Các đường thẳng bên trong chia hình chữ nhật lớn thành 8 hình chữ nhật nhỏ có diện tích bằng nhau.
- Chia 8 phần bằng nhau:
- Có thể chia căn phòng thành 2 hàng và 4 cột, hoặc 4 hàng và 2 cột, tạo ra tổng cộng 8 ô vuông hoặc chữ nhật nhỏ bằng nhau.
- Ví dụ: Chia bằng 3 đường dọc và 1 đường ngang, hoặc 1 đường dọc và 3 đường ngang (tùy thuộc vào kích thước phòng và cách chia). Tổng cộng sẽ có 4 đường chia (1 ngang, 3 dọc hoặc ngược lại).
- Đường đi một lượt, không chồng lấn và bao trọn chu vi:
- Robot có thể bắt đầu ở một góc, di chuyển theo đường viền ngoài để bao trọn chu vi.
- Sau khi hoàn thành chu vi, robot dùng các góc để rẽ vào các đường chia bên trong và đi ra lại đường viền để tiếp tục đi hết các đường chia còn lại, đảm bảo toàn bộ đường đi là một nét liền (một lượt) và không đi qua cùng một đoạn hai lần (không chồng lên đường đã lau).
Ví dụ về đường đi:
- Bắt đầu từ góc dưới bên trái (A).
- Đi lên mép tường trái $\rightarrow$ góc trên bên trái (B).
- Đi sang mép tường trên $\rightarrow$ góc trên bên phải (C).
- Tại (C), robot đi vào đường chia thứ nhất (dọc xuống).
- Đi hết đường chia thứ nhất $\rightarrow$ mép tường dưới.
- Đi một đoạn trên mép tường dưới $\rightarrow$ điểm xuất phát của đường chia thứ hai.
- Đi lên đường chia thứ hai $\rightarrow$ mép tường trên.
- Đi một đoạn trên mép tường trên $\rightarrow$ điểm xuất phát của đường chia thứ ba...
- Tiếp tục đi như vậy để hoàn thành tất cả các đường chia bên trong.
- Cuối cùng, hoàn thành đoạn cuối cùng của chu vi ngoài (ví dụ: mép tường dưới từ điểm cuối cùng của đường chia gần góc A nhất $\rightarrow$ A), kết thúc tại điểm xuất phát (A).
Mấu chốt là: Đường đi bao gồm tất cả các cạnh của 8 hình chữ nhật nhỏ mà không đi chồng lên nhau. Đây chính là bài toán tìm chu trình Euler hoặc đường đi Euler trên đồ thị lưới. Vì mỗi đỉnh trong đồ thị lưới này có bậc chẵn (trừ 2 đỉnh đầu và cuối của đường đi, nếu là đường đi Euler) nên việc vẽ bằng một nét liền là hoàn toàn khả thi.
