Đẩy Hộp

Điểm: 1,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie đang ở trong một cái kho hình chữ nhật kích thước $N \times M$ ô vuông. Mỗi ô có thể là ô trống (.), chướng ngại vật (#), vị trí của Bessie (A), hoặc vị trí của hộp (B). Bessie có thể di chuyển lên, xuống, trái, phải sang các ô trống liền kề (không phải chướng ngại vật và không phải ô chứa hộp).

Khi Bessie di chuyển vào ô chứa hộp, cô sẽ đẩy hộp theo cùng hướng đó — hộp dịch chuyển sang ô tiếp theo theo hướng di chuyển của Bessie. Nếu ô tiếp theo của hộp là chướng ngại vật hoặc nằm ngoài biên, việc đẩy không hợp lệ và Bessie không thể thực hiện bước đó.

Cho $Q$ truy vấn, mỗi truy vấn hỏi: Bessie có thể đẩy hộp đến ô $(r, c)$ hay không?

Dữ liệu vào

Dòng đầu: ba số nguyên $N$ , $M$ , $Q$ .
$N$ dòng tiếp theo: mô tả lưới kho, mỗi dòng gồm $M$ ký tự (#, ., A, B).
$Q$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $r$ , $c$ — tọa độ ô đích (1-indexed).

Dữ liệu ra

Với mỗi truy vấn, in YES nếu Bessie có thể đẩy hộp đến ô $(r, c)$ , ngược lại in NO.

Ràng buộc

$1 \leq N, M \leq 1500$
$1 \leq Q \leq 10^{5}$
Đúng một ô là A và đúng một ô là B.
Ô đích $(r, c)$ của mỗi truy vấn luôn là ô trống hoặc ô B.

Ví dụ

Input	Output	Giải thích
5 5 4 ##.## ##.## A.B.. ##.## ##.## 3 2 3 5 1 3 5 3	NO YES NO NO	Hộp ban đầu ở (3,3). Bessie ở (3,1). Bessie có thể đẩy hộp sang phải (hướng Đông) đến (3,4) và (3,5). Không thể đẩy hộp lên/xuống vì có chướng ngại vật.
5 5 16 ..... .###. .#.#. A.B.. ##.## 1 1 1 2 1 3 1 4 1 5 2 1 2 5 3 1 3 3 3 5 4 1 4 2 4 3 4 4 4 5 5 3	NO NO NO NO NO NO NO NO NO NO YES YES YES YES YES NO	Hộp chỉ có thể đến được các ô ở hàng 4 (từ (4,1) đến (4,5)) trừ (4,5) bị chặn bởi `#` ở hàng 5.

Ghi chú

Đây là bài toán từ USACO December 2017 Platinum, Problem 2.

Bình luận

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