Robot thông minh

Điểm: 0,50 (OI)

Giới hạn thời gian: 0.5s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Nguồn bài:

Viettel Programming Challenge 2023

Dạng bài

Ngôn ngữ cho phép

Output Only

Tải input tại đây: inputs.zip

Với nhu cầu ngày càng lớn sử dụng đồ gia dụng thông minh trong nhà của người Việt Nam, VT lên kế hoạch tham gia vào thị trường này, bắt đầu với việc sản xuất Robot thông minh lau hút bụi nhà. Trước tiên cần đánh giá mức độ khả thi của dự án, công ty đánh giá các bài toán con cần giải quyết để xem nhân sự có đáp ứng được việc tự sản xuất hay không. Một trong các bài toán con cần giải quyết là với mặt sàn của một căn phòng làm sao có thể lập kế hoạch để robot có thể di chuyển được hết mặt sàn của căn phòng. Bài toán được mô hình hoá như sau:

Coi sàn của căn phòng là một bảng được chia thành lưới ô vuông kích thước ~n\times m~, trong đó sẽ có một số ô có vật cản robot không thể đi vào, còn lại các ô khác trống robot có thể di chuyển thoải mái.
~2~ hàng và ~2~ cột là cạnh của bảng tương ứng với các bức tường và robot không thể di chuyển ra được nên các ô trên các vị trí này đều là các vật cản.
Có một ô là vị trí bắt đầu của robot.
Robot sẽ di chuyển theo một tập lệnh độ dài ~k~ mô tả hành trình di chuyển của robot.
Robot sẽ thực hiện lần lượt các lệnh, mỗi lệnh di chuyển robot sẽ di chuyển theo một trong bốn hướng (trên, dưới, trái phải) đến khi gặp vật cản thì dừng lại, sau đó thực hiện lệnh di chuyển tiếp theo.

Bây giờ đội được giao giải quyết bài toán này cần đánh giá xem mức độ hiệu quả mà đội có thể giải quyết bài toán này. Để dễ đánh giá độ hiệu quả, đội sẽ tạo ra một tập lệnh gồm ~k~ lệnh và cho robot di chuyển theo các lệnh này và kiểm tra xem robot có thể di chuyển qua được bao nhiêu ô khác nhau (nếu một ô robot di chuyển qua nhiều lần chỉ được tính một lần).

Yêu cầu: Cho bảng mô tả sàn của một căn phòng, các ô có vật cản, vị trí bắt đầu của robot và số ~k~, hãy tạo ra tập có ~k~ lệnh sao cho robot di chuyển hiệu quả nhất có thể.

Input

Thí sinh được cung cấp ~10~ file dữ liệu đầu vào với tên tương ứng là: input_0.txt, input_1.txt, ..., input_9.txt. Mỗi file dữ liệu đầu vào có khuôn dạng như sau:

Dòng đầu chứa ba số nguyên ~n, m, k~ (~3 \le n, m, k \le 2000~).
Tiếp theo là ~n~ dòng mỗi dòng chứa một xâu ~m~ kí tự, với "#" mô tả ô có vật cản, "." là ô trống, "O" là ô xuất phát của robot. Dữ liệu đảm bảo có đúng ~1~ ô "O".

Output

Đối với mỗi file dữ liệu đầu vào, thí sinh cần nộp một file kết quả đầu ra mô tả tập ~k~ lệnh, các file kết quả đầu ra có tên tương ứng là: output_0.txt, output_1.txt, ..., output_9.txt. Mỗi file kết quả đầu ra có khuôn dạng là một chuỗi kí tự có độ dài bằng $k$ gồm các kí tự 'L', 'R', 'U', 'D' tương ứng với:

'L' lệnh yêu cầu robot di chuyển về phía bên trái bảng.
'R' lệnh yêu cầu robot di chuyển về phía bên phải bảng.
'U' lệnh yêu cầu robot di chuyển về phía bên trên bảng.
'D' lệnh yêu cầu robot di chuyển về phía bên dưới bảng.

Chấm điểm

Đối với mỗi test thí sinh sẽ nhận được ~0~ điểm nếu đưa ra output không hợp lệ, ngược lại thí sinh sẽ nhận được như sau: gọi ~S^*~ là số ô robot có thể di chuyển đến trong lời giải của tác giả và ~S~ là số ô robot có thể di chuyển đến trong lời giải của thí sinh, điểm thí sinh nhận được cho mỗi test sẽ là ~\min(1.0, (\frac{S}{S^*})) \times 100~.

Điểm tối đa của một test là ~100~ điểm. Điểm tối đa của bài là ~1000~ điểm.

Điểm của một lần nộp bài là tổng điểm của các test trong bài nộp đó. Điểm của toàn bộ bài là điểm của lần nộp có số điểm cao nhất.