Толкни коробку
Толкни коробку
Беси и её друзья придумали новую игру "Затолкай ящик вокруг амбара в правый угол не сдвигая сено". Амбар может быть представлен прямоугольной решёткой n * m. В некоторых ячейках решётки находится сено. Беси находится в одной ячейке этой решётки, а большой деревянный ящик занимает другую. Беси и этот ящик не помещаются в одной ячейке одновременно, также они не могут заходить в ячейку с сеном.
Бесси может двигаться в 4 ортогональных направлениях (север, юг, запад, восток) пока не уткнётся в ячейку с сеном. Если она попытается войти в ячейку с ящиком, то ящик продвинется на одну ячейку в этом же направлении, если там есть свободная ячейка. Если свободной ячейки нет, Беси не может сдвинуть ящик.
Определённая ячейка решётки указана как цель. Беси должна доставить ящик в это место.
По заданному описанию амбара, включая начальную позицию ящика и коровы, а также целевую позицию ящика, определите можно ли победить в игре.
Входные данные
Первая строка ввода содержит три числа n, m (1 ≤ n, m ≤ 1500), q (1 ≤ q ≤ 50000), где n - количество строк, m - количество столбцов.
Следующие n строк описывают решётку, где символ '.' показывает пустую ячейку, '#' - ячейку с сеном, 'A' - стартовую позицию Беси, 'B' - начальное положение ящика.
Далее следуют q строк, каждая из которых содержит пару чисел (r, c). Для каждой пары Вы должны определить, возможно ли доставить ящик в эту ячейку, со строкой r, столбцом c, из начального состояния амбара. Верхняя строка имеет номер 1, левый столбец имеет номер 1.
Выходные данные
Выведите q строк, каждая содержит одну из строк "YES" или "NO".
Пояснение
Чтобы переместить ящик в позицию (3, 5) корова просто должна сделать 3 шага вправо.
Все другие позиции не достижимы.
5 5 4 ##.## ##.## A.B.. ##.## ##.## 3 2 3 5 1 3 5 3
NO YES NO NO