Alice thiết kế trò chơi điều khiển robot như sau: Một robot đặt trên một sân được biểu diễn như một lưới ô vuông kích thước . Các dòng được đánh số từ 0 đến , các cột được đánh số từ 0 đến . Ô nằm giao giữa hàng cột được gọi là ô , một số ô của lưới là tường, các ô còn lại là ô tự do. Người chơi điều khiển robot bằng bốn loại lệnh: U, D, L, R, giả sử robot đang đứng tại ô , robot sẽ di chuyển tương ứng như sau:
Lệnh U: Nếu hoặc là tường, robot sẽ không di chuyển. Ngược lại, robot sẽ di chuyển đến .
Lệnh D: Nếu hoặc là tường, robot sẽ không di chuyển. Ngược lại, robot sẽ di chuyển đến .
Lệnh L: Nếu hoặc là tường, robot sẽ không di chuyển. Ngược lại, robot sẽ di chuyển đến .
Lệnh R: Nếu hoặc là tường, robot sẽ không di chuyển. Ngược lại, robot sẽ di chuyển đến .
Người chơi không được biết chính xác vị trí ban đầu của robot, chỉ biết rằng robot có thể đang ở một trong ô tự do .
Yêu cầu: Hãy tìm một dãy lệnh điều khiển robot để robot luôn kết thúc tại vị trí .
Dữ liệu:
Dòng đầu chứa ba số nguyên dương ();
Dòng thứ trong dòng tiếp theo chứa số mô tả lưới, số thứ bằng 0 (hoặc 1) tương ứng ô là không có tường (hoặc có tường);
Dòng thứ trong dòng tiếp theo, mỗi dòng chứa hai số .
Dữ liệu đảm bảo bài toán luôn có cách di chuyển thỏa mãn.
Kết quả:
Ghi ra một dòng chứa một xâu chỉ gồm các kí tự L, R, U, D mô tả dãy lệnh.
Ví dụ:
Dữ liệu:
2 2 2
0 0
1 0
0 1
1 1
Kết quả:
UL
Giải thích:
Nếu ban đầu robot ở ô (0, 1) thì vị trí robot sau mỗi lệnh tương ứng như sau: .
Nếu ban đầu robot ở ô (1, 1) thì vị trí robot sau mỗi lệnh tương ứng như sau: .
