Phillip và Các Đoàn Tàu

Điểm: 5,00 (OI)

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

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

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Đường hầm được biểu diễn dưới dạng một lưới chữ nhật gồm ba hàng và $n$ cột. Người chơi (ký hiệu s) khởi đầu tại ô nằm ở cột ngoài cùng bên trái (cột $1$ ), trên một trong ba hàng. Mục tiêu là tới được cột ngoài cùng bên phải (cột $n$ ).

Trên lưới có $k$ đoàn tàu, mỗi đoàn tàu nằm trọn trong một hàng và gồm từ $2$ ô liên tiếp trở lên. Các đoàn tàu khác nhau được đánh dấu bằng các chữ cái viết hoa khác nhau. Ô trống được ký hiệu ..

Các bước di chuyển trong mỗi lượt diễn ra theo đúng thứ tự sau:

Trước tiên, người chơi đi sang phải đúng một ô.
Sau đó, người chơi có thể đi lên một hàng, đi xuống một hàng, hoặc đứng yên.
Cuối cùng, tất cả đoàn tàu đồng thời dịch sang trái hai ô.

Nếu tại bất kỳ thời điểm nào người chơi và một đoàn tàu cùng nằm trong một ô (kể cả ngay sau bước 1, bước 2 hoặc trong quá trình tàu dịch chuyển ở bước 3), người chơi thua. Tàu khi đi ra khỏi cột $1$ vẫn tiếp tục di chuyển và rời khỏi đường hầm.

Hãy xác định liệu người chơi có chuỗi nước đi nào để tới được cột $n$ hay không.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $t$ — số bộ dữ liệu ( $1 \leq t \leq 10$ ).
Với mỗi bộ dữ liệu:
- Dòng đầu chứa hai số nguyên $n$ và $k$ ( $2 \leq n \leq 100$ , $1 \leq k \leq 26$ ).
- Ba dòng tiếp theo, mỗi dòng gồm $n$ ký tự mô tả một hàng của lưới (ký tự s xuất hiện đúng một lần ở cột đầu tiên).

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra YES nếu người chơi có thể tới được cột $n$ , ngược lại in NO.

Ràng buộc

$1 \leq t \leq 10$
$2 \leq n \leq 100$
$1 \leq k \leq 26$

Ví dụ

Input	Output	Giải thích
2 10 4 s.ZZ...... .....AAABB .YYYYYY... 10 4 s.ZZ...... ....AAAABB .YYYYYY...	YES NO	Trong bộ thứ nhất, người chơi có thể luồn qua khoảng trống và thoát ra cột cuối. Trong bộ thứ hai, mọi nước đi đều dẫn đến va chạm với một đoàn tàu.
2 16 4 ...AAAAA........ s.BBB......CCCCC ........DDDDD... 16 4 ...AAAAA........ s.BBB....CCCCC.. .......DDDDD....	YES NO	Ở bộ thứ nhất, người chơi đi tiến rồi đi xuống hàng dưới, đi tiếp, đi lên hàng giữa, rồi cuối cùng đi lên hàng trên để vượt qua.

Bình luận

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