trang chủ / đề bài / icpcwf23_f

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 h×w ô 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 h và w (1≤h,w≤500) là chiều cao và chiều rộng của bảng.

Tiếp theo là h 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 w 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 h 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

  • 1≤h,w≤500.
  • Mỗi ô là . hoặc một chữ cái thường a đến z.

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 1, sang phải đưa nó về cột 7, nghiêng lên hay xuống không làm gì. Không thể đưa nó về cột 3.
4 3
yr.
..b
ry.
b..

...
..b
.ry
byb
no Ban đầu có 2 viên gạch màu r và 2 viên màu b, nhưng cách sắp xếp kết thúc có 1 viên màu r và 3 viên màu b. Nghiêng bảng không đổi màu viên gạch nào.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0