Nghiêng bảng gạch
Đề bài
Mô tả
Bạn tìm thấy một trò chơi xếp hình lạ trong một chiếc hộp đựng đồ chơi cũ trên gác mái. Trò chơi là một bảng hình chữ nhật gồm ô vuông. Một số ô của bảng có đặt một viên gạch màu.
Bạn chưa rõ mục tiêu chính xác của trò chơi là gì, nhưng bạn bắt đầu tìm hiểu các cách sắp xếp lại các viên gạch. Có thể thay đổi cách sắp xếp bằng cách nghiêng bảng theo một trong bốn hướng: sang trái, sang phải, về phía bạn (xuống dưới) hoặc ra xa bạn (lên trên). Khi nghiêng, mọi viên gạch trượt theo hướng đó cho đến khi bị chặn bởi biên của bảng hoặc bởi một viên gạch khác.
Cho cách sắp xếp ban đầu và cách sắp xếp kết thúc, hãy xác định có tồn tại một dãy các lần nghiêng (có thể rỗng) biến cách sắp xếp ban đầu thành cách sắp xếp kết thúc hay không.
Hình dưới minh họa lời giải của ví dụ thứ nhất (bấm các bước để xem từng lần nghiêng; màu ô tương ứng với màu gạch):
grid .r.. rgyb .b.. .yr. step Trạng thái ban đầu highlight red 1,2 2,1 4,3 highlight green 2,2 highlight blue 2,4 3,2 highlight orange 2,3 4,2 step Nghiêng sang trái clear set 1,1 r set 1,2 . set 3,1 b set 3,2 . set 4,1 y set 4,2 r set 4,3 . highlight red 1,1 2,1 4,2 highlight green 2,2 highlight blue 2,4 3,1 highlight orange 2,3 4,1 step Nghiêng về phía bạn clear set 2,2 . set 2,3 . set 2,4 . set 3,2 g set 4,3 y set 4,4 b highlight red 1,1 2,1 4,2 highlight green 3,2 highlight blue 3,1 4,4 highlight orange 4,1 4,3 step Nghiêng sang phải clear set 1,1 . set 1,4 r set 2,1 . set 2,4 r set 3,1 . set 3,2 . set 3,3 b set 3,4 g highlight red 1,4 2,4 4,2 highlight green 3,4 highlight blue 3,3 4,4 highlight orange 4,1 4,3 step Nghiêng ra xa bạn clear set 1,1 y set 1,2 r set 1,3 b set 2,3 y set 3,3 . set 4,1 . set 4,2 . set 4,3 . highlight red 1,2 1,4 2,4 highlight green 3,4 highlight blue 1,3 4,4 highlight orange 1,1 2,3
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và () là chiều cao và chiều rộng của bảng.
Tiếp theo là dòng mô tả cách sắp xếp ban đầu, từ hàng trên cùng đến hàng dưới cùng. Mỗi dòng là một xâu độ dài mô tả các ô của hàng đó từ trái sang phải. Ô trống được biểu diễn bằng dấu chấm (.). Ô có gạch được biểu diễn bằng màu của viên gạch, là một chữ cái thường (a đến z). Các chữ cái khác nhau biểu diễn các màu khác nhau, và các viên gạch cùng màu không phân biệt được với nhau.
Sau cách sắp xếp ban đầu là một dòng trống, rồi đến mô tả cách sắp xếp kết thúc gồm dòng theo cùng định dạng.
Dữ liệu ra
In ra yes nếu tồn tại một dãy các lần nghiêng biến cách sắp xếp ban đầu thành cách sắp xếp kết thúc, ngược lại in ra no.
Ràng buộc
- .
- Mỗi ô là
.hoặc một chữ cái thườngađếnz.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 4 .r.. rgyb .b.. .yr. yrbr ..yr ...g ...b |
yes | Nghiêng lần lượt sang trái, về phía bạn, sang phải, ra xa bạn (như trong hình). |
| 1 7 ....x.. ..x.... |
no | Chỉ có một viên gạch trên một hàng: nghiêng sang trái đưa nó về cột , sang phải đưa nó về cột , nghiêng lên hay xuống không làm gì. Không thể đưa nó về cột . |
| 4 3 yr. ..b ry. b.. ... ..b .ry byb |
no | Ban đầu có viên gạch màu r và viên màu b, nhưng cách sắp xếp kết thúc có viên màu r và viên màu b. Nghiêng bảng không đổi màu viên gạch nào. |
Bình luận