Hang băng
Đề bài
Mô tả
Bạn đang ở một tầng của hang băng nhiều tầng. Để đi tiếp, bạn phải rơi xuống tầng dưới, và cách duy nhất là rơi xuyên qua lớp băng.
Tầng hang hiện tại là một lưới chữ nhật gồm hàng và cột. Mỗi ô chứa băng nguyên vẹn hoặc băng đã nứt. Từ ô đang đứng, bạn chỉ có thể bước sang một ô kề cạnh (không được đứng yên tại chỗ). Khi bạn bước sang một ô:
- Nếu ô đó là băng đã nứt, bạn rơi xuyên qua ô đó xuống tầng dưới.
- Nếu ô đó là băng nguyên vẹn, lớp băng ở ô đó bị nứt và bạn đứng lại trên ô đó.
Các hàng được đánh số từ đến từ trên xuống dưới, các cột được đánh số từ đến từ trái sang phải. Ký hiệu là ô ở hàng , cột .
Bạn đang đứng ở ô , và ô này đã nứt vì bạn vừa rơi từ tầng trên xuống đây. Lối ra xuống tầng kế tiếp nằm ở ô , nên bạn cần rơi xuyên qua đúng ô . Ô lối ra có thể trùng với ô bạn đang đứng.
Hãy xác định xem bạn có thực hiện được điều đó hay không.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên và .
- dòng tiếp theo mô tả trạng thái ban đầu của tầng hang, mỗi dòng gồm ký tự "." (băng nguyên vẹn) hoặc "X" (băng đã nứt).
- Dòng tiếp theo chứa hai số nguyên và là vị trí ban đầu của bạn. Dữ liệu đảm bảo ô là ký tự "X".
- Dòng cuối chứa hai số nguyên và là toạ độ ô mà bạn cần rơi xuyên qua.
Dữ liệu ra
In ra YES nếu bạn tới được đích, ngược lại in ra NO.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 6 X...XX ...XX. .X..X. ...... 1 6 2 2 |
YES | Ô đích ban đầu là băng nguyên vẹn. Bạn đi tới đó một lần làm băng nứt ra, rời đi rồi quay lại; lần bước vào thứ hai bạn rơi xuyên qua đúng ô cần tới. |
| 5 4 .X.. ...X X.X. .... .XX. 5 3 1 1 |
NO | Không có cách nào rơi xuyên qua ô . |
| 4 7 ..X.XX. .XX..X. X...X.. X...... 2 2 1 6 |
YES | Ô đích vốn đã nứt sẵn, nên chỉ cần đi tới một ô kề nó rồi bước sang là rơi xuống ngay. |
Bình luận