Description

Translated from USACO 2017 December Contest, Platinum Problem 2: Push a Box.

A barn is an $N \times M$ rectangular grid, and some cells contain hay bales. Bessie stands in one cell, and a large crate occupies another cell. Bessie cannot be in the same cell as the crate, nor in the same cell as a hay bale.

From any empty cell, she may move to any of its four orthogonally adjacent cells (north, south, east, west). If she attempts to move into the cell containing the crate, the crate is pushed one cell further in the same direction, provided the next cell in that direction is within bounds and empty (i.e., not a hay bale or outside the grid); otherwise, the move is not allowed. After a successful push, Bessie occupies the crate’s previous cell.

Given the barn layout (empty cells, hay bales, and the crate), along with Bessie’s starting position and the target positions for the crate, determine whether Bessie can push the crate to each specified target cell.

Input Format

The first line contains three integers $N, M, Q$, where $N$ is the number of rows, $M$ is the number of columns, and $Q$ is the number of queries.

The next $N$ lines describe the initial layout of the barn, where . denotes an empty cell, # denotes a hay bale, A denotes Bessie’s initial position, and B denotes the crate’s initial position.

The next $Q$ lines each contain a coordinate $(R, C)$, representing row $R$ and column $C$. For each line, determine whether Bessie can push the crate to this cell.

Output Format

Output $Q$ lines. For each query, print YES if Bessie can push the crate to the specified cell; otherwise, print NO.

5 5 4
##.##
##.##
A.B..
##.##
##.##
3 2
3 5
1 3
5 3

NO
YES
NO
NO

Hint

For $100\%$ of the testdata, it is guaranteed that $1 \leq N, M \leq 1500$ and $1 \leq Q \leq 50000$.

Translated by ChatGPT 5