(Analysis by Nathan Pinsker)

One immediate thought that is to use some flavor of graph search to solve this problem, since the state space is fairly tractable and straightforward (it only consists of Bessie's and the box's position). Unfortunately, with $M, N \leq 1,500$, this approach is both too slow and too time-consuming, since it takes $O(N^2M^2)$ space and time. However, notice that this naive approach keeps track of a lot of unnecessary state information. In particular, Bessie's position isn't terribly important to us most of the time -- only the box's position -- and Bessie's position only matters insofar as it determines where the box will be pushed next. In other words, we don't actually care about Bessie's precise position, only from which directions she can push the box at the next step.

We can take advantage of this insight by redefining our state slightly. It still consists of Bessie's and the box's position, but we limit ourselves to considering only states where Bessie is directly next to the box. This is $O(MN)$ states, which is possible to work with.

However, the state transition becomes more complicated as a result. Bessie can transition between states in one of two ways: either she can push the box, or she can walk around the box and reach another side. The first type of transition is easy to handle, so we turn our attention to handling the second type. Handling this type of transition is equivalent to asking "Can I get from point A to point B, without walking over the square containing the box?" Luckily, this question is well-studied, and is known as biconnected components. We consider the lattice graph formed by taking each unoccupied spot in the barn as a vertex and edges between each pair of adjacent vertices. Since A and B are clearly part of the same connected component, there is an alternate path from A to B if and only if they are part of the same biconnected component in this graph.

Therefore, we can solve the problem by precomputing all biconnected components of the lattice graph described above. We perform a BFS over our $O(NM)$ states; if we want to check whether Bessie can walk around the box to reach another side without moving it, we simply query our graph to see if Bessie's start and end vertex are part of the same biconnected component. This operation is $O(1)$, so our overall BFS runtime will be $O(NM)$. The runtime of our biconnected components algorithm is also $O(NM)$. Once we have run these two algorithms, we can answer queries in $O(1)$ time, so our overall running time is $O(NM + Q)$.

Travis's solution is below:

#include <cstdio>
#include <cassert>
#include <vector>
using namespace std;

#define NMAX 1500

struct P {
int x, y;
P(int x, int y): x(x), y(y) { }
P() {}
bool operator ==(P b) {
return x == b.x && y == b.y;
}
bool operator !=(P b) {
return !(x == b.x && y == b.y);
}
};

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

int getDIndex(P v1, P v2) {
for (int d = 0; d < 4; d++) {
if (v1.x + dx[d] == v2.x && v1.y + dy[d] == v2.y) {
return d;
}
}
assert(false);
}

int width, height;
int blockStartX, blockStartY;
int blockEndX, blockEndY;
int humanStartX, humanStartY;

bool isOpen[NMAX][NMAX];

bool visited[NMAX][NMAX];
int depth[NMAX][NMAX];
int low[NMAX][NMAX];

int initialD = -1;

void biconnected_component_dfs(P v, P parent, int myDepth) {
visited[v.x][v.y] = true;
depth[v.x][v.y] = myDepth;
low[v.x][v.y] = myDepth;
int childCount = 0;

vector<vector<P>> components;

for (int d = 0; d < 4; d++) {
int x1 = v.x + dx[d];
int y1 = v.y + dy[d];
if (x1 >= 0 && x1 < width && y1 >= 0 && y1 < height && isOpen[x1][y1]) {
if (!visited[x1][y1]) {
if (x1 == blockStartX && y1 == blockStartY) {
initialD = (d + 2) % 4;
}

for (int d2 = 0; d2 < 4; d2++) {
int x2 = v.x + dx[d2];
int y2 = v.y + dy[d2];
alreadyVisited[d2] = (x2 >= 0 && x2 < width && y2 >= 0 && y2 < height && isOpen[x2][y2] && visited[x2][y2]);
}

biconnected_component_dfs(P(x1, y1), v, myDepth+1);
childCount++;
if (low[x1][y1] >= depth[v.x][v.y]) {
vector<P> cmp;

for (int d2 = 0; d2 < 4; d2++) {
int x2 = v.x + dx[d2];
int y2 = v.y + dy[d2];
if (x2 >= 0 && x2 < width && y2 >= 0 && y2 < height && isOpen[x2][y2] && visited[x2][y2] && !alreadyVisited[d2]) {
cmp.push_back(P(x2,y2));
}
}

components.push_back(cmp);
}
low[v.x][v.y] = min(low[v.x][v.y], low[x1][y1]);
} else {
if (parent != P(x1,y1)) {
low[v.x][v.y] = min(low[v.x][v.y], depth[x1][y1]);
}
}
}
}

vector<P> lastComponent;
for (int d = 0; d < 4; d++) {
int x1 = v.x + dx[d];
int y1 = v.y + dy[d];
if (x1 >= 0 && x1 < width && y1 >= 0 && y1 < height && isOpen[x1][y1]) {
bool exist = false;
for (int i = 0; i < components.size(); i++) {
for (int j = 0; j < components[i].size(); j++) {
if (components[i][j] == P(x1,y1)) {
exist = true;
}
}
}
if (!exist) {
lastComponent.push_back(P(x1,y1));
}
}
}
if (lastComponent.size() > 0) {
components.push_back(lastComponent);
}

unsigned short bits = 0;

for (auto& component : components) {
for (int i = 1; i < component.size(); i++) {
int dIndex = getDIndex(v, component[i-1]);
int dIndex2 = getDIndex(v, component[i]);
bits |= ((unsigned short)1) << (dIndex*4 + dIndex2);
bits |= ((unsigned short)1) << (dIndex2*4 + dIndex);
}
}

}

pair<P, char> bfs[NMAX * NMAX * 4];
bool bfsVisited[NMAX][NMAX][4];
void do_bfs(pair<P, char> startV) {
bfs[0] = startV;
int index = 0;
int len = 1;
for (int i = 0; i < width; i++) {
for (int j = 0; j < height; j++) {
for (int d = 0; d < 4; d++) {
bfsVisited[i][j][d] = false;
}
}
}
bfsVisited[startV.first.x][startV.first.y][(int)startV.second] = true;
while (index < len) {
pair<P, char> v = bfs[index];
index++;

P p = v.first;
int d = v.second;

int x1 = p.x;
int y1 = p.y;
int x2 = x1 - dx[d];
int y2 = y1 - dy[d];
if (x2 >= 0 && x2 < width && y2 >= 0 && y2 < height && isOpen[x2][y2]) {
pair<P, char> w = make_pair(P(x2, y2), d);
if (!bfsVisited[w.first.x][w.first.y][(int)w.second]) {
bfsVisited[w.first.x][w.first.y][(int)w.second] = true;
bfs[len++] = w;
}
}

for (int d1 = 0; d1 < 4; d1++) {
if (adjacency[p.x][p.y] & (((unsigned short)1) << (d*4 + d1))) {
pair<P, char> w = make_pair(P(p.x, p.y), d1);
if (!bfsVisited[w.first.x][w.first.y][(int)w.second]) {
bfsVisited[w.first.x][w.first.y][(int)w.second] = true;
bfs[len++] = w;
}
}
}
}
}

char rowInput[NMAX + 5];

int main() {
int q;
scanf("%d", &height);
scanf("%d", &width);
scanf("%d", &q);
blockStartX = -1;
blockStartY = -1;
humanStartX = -1;
humanStartY = -1;
for (int i = 0; i < height; i++) {
scanf("%s", rowInput);
for (int j = 0; j < width; j++) {
isOpen[j][i] = (rowInput[j] != '#');
if (rowInput[j] == 'A') {
assert(humanStartX == -1);
humanStartX = j;
humanStartY = i;
} else if (rowInput[j] == 'B') {
assert(blockStartX == -1);
blockStartX = j;
blockStartY = i;
} else {
assert(rowInput[j] == '.' || rowInput[j] == '#');
}
}
}

for (int x = 0; x < width; x++) {
for (int y = 0; y < height; y++) {
visited[x][y] = false;
}
}

biconnected_component_dfs(P(humanStartX, humanStartY), P(-1, -1), 0);

if (initialD == -1) {
for (int i = 0; i < q; i++) {
int blockEndX, blockEndY;
scanf("%d", &blockEndY);
scanf("%d", &blockEndX);
blockEndX--;
blockEndY--;
printf("%s\n", blockStartX == blockEndX && blockStartY == blockEndY ? "YES" : "NO");
}
return 0;
}

do_bfs(make_pair(P(blockStartX, blockStartY), (char)initialD));

for (int i = 0; i < q; i++) {
int blockEndX, blockEndY;
scanf("%d", &blockEndY);
scanf("%d", &blockEndX);
blockEndX--;
blockEndY--;
assert(isOpen[blockEndX][blockEndY]);
bool isPossible =
bfsVisited[blockEndX][blockEndY][0] ||
bfsVisited[blockEndX][blockEndY][1] ||
bfsVisited[blockEndX][blockEndY][2] ||
bfsVisited[blockEndX][blockEndY][3];
printf("%s\n", isPossible ? "YES" : "NO");
}
}