Push a Box

题目描述

Bessie 和她的朋友们发明了一个新游戏。这个游戏的名字十分贴切，但并不特别有创意。她们称它为“在谷仓里推箱子把它推到正确位置并且不要移动干草”游戏（如果你觉得这有点夸张，你应该看看奶牛们写代码时用的一些变量名……） 谷仓可以建模为一个 $N \times M$ 的矩形网格。一些网格单元里有干草。Bessie 占据网格中的一个单元，一个大木箱占据另一个单元。Bessie 和箱子不能同时位于同一个单元中，并且它们都不能进入含有干草的单元。 Bessie 可以向 4 个正交方向（北、东、南、西）移动，只要她不走进干草。如果她尝试走到箱子所在的格子，那么箱子会被沿该方向推动一格，前提是箱子另一侧有一个空格。如果没有空格，那么 Bessie 将无法进行这次移动。 某个网格单元被指定为目标位置。Bessie 的目标是把箱子推到该位置。 给定谷仓的布局，包括箱子和奶牛的起始位置，以及箱子的目标位置，判断是否有可能赢得游戏。 注意：本题允许使用 512MB 内存，高于默认的 256MB 限制。

输入格式

第一行包含三个数 $N$, $M$, 和 $Q$，其中 $N$ 为网格的行数，$M$ 为网格的列数。 $1 \le N,M \le 1500$. $1 \le Q \le 50,000$. 接下来 $N$ 行为网格表示，其中字符分别表示空地（.）、干草（#）、Bessie 的起始位置（A）、以及箱子的初始位置（B）。 之后有 $Q$ 行，每行包含一对整数 $(R, C)$。对于每一对数，你需要判断从谷仓的初始状态出发，是否有可能把箱子推到第 $R$ 行第 $C$ 列。最上面一行是第 1 行，最左边一列是第 1 列。

输出格式

$Q$ 行，每行输出字符串 "YES" 或 "NO"。

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

NO
YES
NO
NO

提示

要把箱子推到位置 (3, 5)，奶牛只需要向右移动 3 格。 另外三个位置都无法到达。 题目来源：Nathan Pinsker

标签: USACO|2017|Platinum

来源

USACO|2017|Platinum