Đường đi chẵn
Đề bài
Mô tả
Năm ngoái, Arthur tham gia Olympic Robot Việt Nam với một con robot bị trục trặc. Năm nay, cậu quyết định tham gia thêm một lần nữa.
Thử thách năm nay khó hơn nhiều. Sân chơi là một bảng hình chữ nhật kích thước , gồm hàng đánh số từ đến từ trên xuống dưới và cột đánh số từ đến từ trái sang phải. Ô nằm ở hàng , cột được ký hiệu là . Mỗi ô chứa hoặc một bóng đèn, hoặc một hòn đá (không chứa cả hai). Các bóng đèn có thể bật hoặc tắt. Ban đầu, một số bóng đèn đang bật.
Mục tiêu của thử thách là tắt hết các bóng đèn. Để làm điều đó, robot của các đội có thể thực hiện một số lượt chạy. Trong mỗi lượt chạy, robot bắt đầu ở một ô bất kỳ trên bảng rồi thực hiện một dãy bước di chuyển. Một lượt chạy hợp lệ phải tuân theo các quy tắc sau:
- Mỗi bước, robot phải di chuyển từ vị trí hiện tại sang một ô chung cạnh, tức là sang ô kế tiếp theo một trong bốn hướng: lên, xuống, trái hoặc phải.
- Robot phải luôn ở trong bảng.
- Robot không được đi vào ô có đá.
- Trong một lượt chạy, robot không được đi qua một ô quá một lần. Tuy nhiên, robot có thể đi qua một ô nhiều lần trong các lượt chạy khác nhau.
- Số ô robot đi qua trong một lượt chạy phải là số chẵn.
Từ các quy tắc trên, dễ thấy một lượt chạy hợp lệ được xác định duy nhất bởi bộ , trong đó là vị trí xuất phát và là xâu gồm các ký tự U, D, L, R mô tả dãy bước di chuyển. Ở đây U, D, L, R lần lượt là lên, xuống, trái và phải. Độ dài xâu phải là số lẻ.
Theo luật của cuộc thi, khi thực hiện một lượt chạy, mỗi khi robot đi qua một ô, nó có thể chọn tắt đèn ở ô đó. Tuy nhiên, robot của Arthur lại bị lỗi: nó luôn đổi trạng thái đèn (đang bật thành tắt, đang tắt thành bật) ở mọi ô nó đi qua. Nói cách khác, đèn ở mọi ô trên đường đi của robot (kể cả ô xuất phát và ô kết thúc) đều bị đổi trạng thái.
Với con robot lỗi này, chỉ riêng việc tắt hết đèn đã là khó. Hãy giúp Arthur làm điều đó. Không cần tối thiểu số lượt chạy, nhưng tổng số bước di chuyển trong mọi lượt chạy không được vượt quá .
Dữ liệu vào
Dòng đầu tiên chứa số nguyên : số bộ dữ liệu. Tiếp theo là bộ dữ liệu, mỗi bộ có dạng:
- Dòng đầu tiên chứa hai số nguyên và : kích thước bảng.
- dòng tiếp theo mô tả bảng. Mỗi dòng là một xâu độ dài gồm các ký tự
.,Xhoặc#, trong đó:.là ô có đèn đang tắt,Xlà ô có đèn đang bật,#là ô có đá.
Dữ liệu ra
Với mỗi bộ dữ liệu:
- Nếu không thể tắt hết đèn với tổng không quá bước di chuyển, in ra .
- Ngược lại, dòng đầu tiên chứa số nguyên (): số lượt chạy. Tiếp theo là dòng, mỗi dòng chứa hai số nguyên , và một xâu mô tả một lượt chạy như trên. Tổng độ dài các xâu không được vượt quá .
Nếu có nhiều cách, in ra cách bất kỳ.
Ràng buộc
- .
- .
- Tổng trên mọi bộ dữ liệu không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 5 5 XXXXX XXXX. XX#X. XXXX. XX... |
2 1 1 RRRRDDDDLLLLUUURRRDDLLU 2 5 DDDLL |
Lượt thứ nhất xuất phát từ , đi hết hàng , xuống cột , quay lại theo hàng , lên cột đến , sang phải đến , xuống , sang trái đến rồi lên : đi qua ô, sau lượt này chỉ còn đèn ở , , , , , bật. Lượt thứ hai đi qua đúng ô này. |
| 3 1 1 X 1 3 X.X 2 2 XX .X |
-1 2 1 3 L 1 2 L -1 |
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ nhất và thứ ba có số đèn bật lẻ nên không thể tắt hết. Ở bộ thứ hai, lượt tắt đèn và bật đèn , rồi lượt tắt cả hai. |
Bình luận