NGUỒN: Bài tập thầy Lê Minh Hoàng ôn Tại Hải Phòng T11/2020
Bản đồ một kho hàng là hình chữ nhật kích thước được chia làm lưới ô vuông đơn vị. Các hàng của bảng được đánh số từ tới từ trên xuống dưới và các cột của bảng được đánh số từ tới từ trái qua phải. Ô nằm trên giao của hàng và cột gọi là ô . Trong kho có một số kiện hàng được xếp sẵn, mỗi kiện hàng xếp sẵn chiếm đúng ô.
Robot là một hình chữ nhật chiếm trọn một số ô trống trong kho hàng. Tại mỗi bước, bạn có thể ra lệnh cho robot di chuyển theo một trong bốn hướng song song với cạnh nhà kho. Khi nhận mỗi lệnh di chuyển, robot sẽ đi theo đúng hướng được yêu cầu cho tới khi:
Hoặc robot đi ra khỏi nhà kho (chính xác là khi robot không chiếm ô nào trong nhà kho nữa), nhiệm vụ của bạn hoàn thành;
Hoặc robot vướng vào một kiện hàng đã xếp sẵn theo hướng di chuyển (tức là kiện hàng đó sẽ bị robot đè lên nếu robot di chuyển tiếp), robot dừng lại và đợi lệnh di chuyển tiếp theo của bạn.
Yêu cầu: Tìm một dãy ngắn nhất các lệnh di chuyển đưa robot ra khỏi nhà kho.
Dữ liệu vào:
Dòng đầu chứa hai số nguyên dương cách nhau bởi dấu cách.
dòng tiếp theo, dòng thứ chứa ký tự liền nhau, ký tự thứ thể hiện tình trạng ô của nhà kho theo ý nghĩa sau:
Dấu thăng “#”: Ô có một kiện hàng xếp sẵn;
Dấu chấm “.” Ô là ô trống;
Chữ “R”: Ô đang bị robot chiếm chỗ.
Dữ liệu vào đảm bảo các ô chứa chữ R tạo thành một hình chữ nhật ứng với vị trí khởi đầu của robot.
Dữ liệu ra:
Ghi ra một số nguyên duy nhất là số lệnh di chuyển để đưa robot ra khỏi nhà kho. Nếu không tồn tại dãy lệnh di chuyển để đưa robot ra khỏi nhà kho, ghi ra số .
