Push a Box#10519
Bessie and her friends have invented a new game. The game has been given an appropriately descriptive, though not particularly creative, name. They call it the "Push A Box Around The Barn To Get It In The Right Spot And Don't Move The Hay" game (if you think that's excessive, you should see some of the variable names the cows use when they write code...)
The barn can be modeled as an n \times m rectangular grid. Some of the grid cells contain hay. Bessie occupies one cell of the grid, while a large wooden box occupies another. Bessie and the box cannot occupy the same cell at the same time, and neither can occupy a cell containing hay.
Bessie can move in the orthogonal directions (north, east, south, and west) as long as she does not move into a cell containing hay. If she attempts to move into the cell occupied by the box, the box will be pushed one cell in that direction, provided that the cell on the other side of the box is empty. If that cell is not empty, Bessie cannot make that move.
One grid cell is designated as the goal. Bessie's goal is to move the box to that cell.
Given the layout of the barn, including the initial positions of Bessie and the box, determine whether it is possible to move the box to the target position.
The first line contains three integers n, m~(1 \le n, m \le 1500) and q~(1 \le q \le 50000), where is the number of rows in the grid and is the number of columns.
The next lines describe the grid. Each character represents an empty cell '', a cell containing hay '#', Bessie's starting position '', or the box's initial position ''.
This is followed by lines, each containing a pair of integers . For each pair, determine whether it is possible to move the box to the cell in row , column , starting from the initial state of the barn. The top row is row , and the leftmost column is column .
Print lines, each containing either "YES" or "NO".
To move the box to position , Bessie only needs to move spaces to the right.
None of the other three positions can be reached.
Example 1