#PU769. USACO 2017 December Contest, Platinum — Problem 2. Push a Box

    ID: 1253 传统题 文件IO:pushabox 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:dec17来源:usaco.orgscoring:equal_test_cases广搜

USACO 2017 December Contest, Platinum — Problem 2. Push a Box

USACO 2017 December Contest, Platinum — Problem 2. Push a Box

题目描述

Bessie and her friends have invented a new game. The game is named accurately, but not particularly creatively. 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×MN \times M rectangular grid. Some of the grid cells have hay in them. Bessie occupies one cell in this grid, and a large wooden box occupies another cell. Bessie and the box are not able to fit in the same cell at the same time, and neither can fit into a cell containing hay. Bessie can move in the 4 orthogonal directions (north, east, south, west) as long as she does not walk into hay. If she attempts to walk to the space with the box, then the box will be pushed one space in that direction, as long as there is an empty cell on the other side. If there is no empty cell, then Bessie will not be able to make that move. A certain grid cell is designated as the goal. Bessie's goal is to get the box into that location. Given the layout of the barn, including the starting positions of the box and the cow, and the target position of the box, determine if it possible to win the game.

输入格式

The first line has three numbers, NN, MM, and QQ, where NN is the number of rows in the grid and MM is the number of columns. 1≤N,M≤15001 \le N,M \le 1500. 1≤Q≤50,0001 \le Q \le 50,000. On the next NN lines is a representation of the grid, where characters represent empty cells (.), hay (#), Bessie's starting position (A), and the box's initial location (B). This is followed by QQ lines, each with a pair of integers (R,C)(R, C). For each pair, you should determine if it is possible to get the box to that cell at row RR, column CC, starting from the initial state of the barn. The top row is row 1, and the left column is column 1.

输出格式

QQ lines, each with either the string "YES" or "NO".

数据范围

(见题面原文)

样例

样例 1

5 5 4
##.##
##.##
A.B..
##.##
##.##
3 2
3 5
1 3
5 3
NO
YES
NO
NO
To push the box to the position (3, 5), the cow just needs to move 3 spaces to
the right.
None of the other three positions are attainable.
Problem credits: Nathan Pinsker