#8251. 「USACO 2017.12 Platinum」Push a Box NOI/NOI+/CTSC

时间限制:1000 ms 内存限制:512 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: jxy2012

题目描述

题目译自 USACO 2017 December Contest, Platinum Problem 2. Push a Box

一个谷仓是一个 的矩形网格,有一些网格里有干草。 Bessie 站在其中一个格子内,还有一个格子里有一个大木箱。 Bessie 不能和大木箱在一个格子里,也不能和干草在一个格子里。

如果她不与干草在同一个格子,她就可以往自己旁边的四个方向(东西南北)移动,如果她想移动到有木箱的格子里,那个木箱就会被她推一格(只要木箱的那个方向还有空间),如果没有空间,那 Bessie 就不能移动了。

给你谷仓的布局(空格子,干草以及木箱位置)以及 Bessie 的出发位置和箱子要被推到的位置,请你帮忙计算 Bessie 能不能把木箱推到指定位置。

输入格式

第一行有三个数 ,其中 是谷仓的行数, 是列数, 是询问数。

接下来 行是谷仓的初始布局,其中 . 代表空格子, # 代表干草格子, A 代表 Bessie 的初始位置, B 是木箱的初始位置。

接下来 行,每行一个坐标 ,代表第 行第 行。对于每行,你要输出 Bessie 是否有可能把箱子推到这个位置。

输出格式

行,每行一个答案,如果 Bessie 能走到,输出 YES ,否则输出 NO

样例

样例输入

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

样例输出

NO
YES
NO
NO

样例解释

为了把箱子推到 ,奶牛只需要向右移动三格。

其他的三个位置均不可达。

数据范围与提示

对于 的数据,保证