题解

思路分析

「推箱子」的离线判定问题。Bessie 能否把箱子推到目标格，本质上是判断在合法走动、推箱的规则下的可达状态。做法分为三步：

1. Tarjan + DFS 找出 Bessie 可自由行走的区域：将地图看成图，把空地构成的连通块缩点，得到 Bessie 在不推箱子时可以随意往返的区域。
2. 从起点 BFS 找到首个推动方向：若 Bessie 无法绕到箱子旁边，则直接不可行；否则记录初始箱子位置与推动方向。
3. 状态 DFS / BFS 推箱子：以 “箱子所在格 + 当前推动方向” 为状态搜索。若箱子前后格均为空则可推动；同时对缩点图进行判定，看 Bessie 是否能绕到另一个方向继续推动。

最后在状态表中检查每个询问位置四个方向是否得到访问即可。

#include<bits/stdc++.h>
#define ci const int
using namespace std;
ci N=1505*1505*1.5,M=1505,fx[4]={1,-1,0,0},fy[4]={0,0,1,-1};
int n,m,Q,id[M][M],ax,ay,bx,by,cnt,mp[M][M];
int dfn[N],low[N],st[N],top,dfstime,dep[N],D[N],tot,siz[N],son[N],tp[N],f[N],rt[N];
vector<int>g[N],G[N];
void Add(ci x,ci y){
	G[x].push_back(y),G[y].push_back(x);
}
void tarjan(ci x){
	st[++top]=x,dfn[x]=low[x]=++dfstime;
	for(int y:g[x])
		if(!dfn[y]){
			tarjan(y),low[x]=min(low[x],low[y]);
			if(low[y]==dfn[x]){
				++cnt;
				while(st[top]!=y)Add(st[top--],cnt);
				Add(st[top--],cnt);
				Add(x,cnt);
			}
		}
		else low[x]=min(low[x],dfn[y]);
}
void dfs(ci x){
	dep[x]=dep[f[x]]+1,D[x]=++tot,siz[x]=1;
	if(!rt[x])rt[x]=x;
	for(int y:G[x])
		if(y!=f[x])
			f[y]=x,rt[y]=rt[x],dfs(y),siz[x]+=siz[y],
			son[x]=siz[y]>siz[son[x]]?y:son[x];
}
void DFS(ci x){
	if(!tp[x])tp[x]=x;
	if(son[x])tp[son[x]]=tp[x],DFS(son[x]);
	for(int y:G[x])if(!tp[y])DFS(y);
}
int in(ci x,ci y){
	return D[x]<=D[y]&&D[y]<D[x]+siz[x];
}
int lca(int x,int y){
	int fx=tp[x],fy=tp[y];
	while(fx!=fy){
		if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
		x=f[fx],fx=tp[x];
	}
	return dep[x]<dep[y]?x:y;
}
bool check(ci x,ci y,ci a){
	if(rt[x]!=rt[y])return 1;
	ci l=lca(x,y);
	if(a==l)return 1;
	return (in(l,a)&&in(a,x))||(in(l,a)&&in(a,y));
}
bool vis[M][M][4];
struct node{
	int x,y,d;
};
queue<node>q;
void ins(ci x,ci y,ci d){
	if(!vis[x][y][d])vis[x][y][d]=1,q.push({x,y,d});
}
int main(){
	scanf("%d%d%d",&n,&m,&Q);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j){
			id[i][j]=++cnt;
			char c=getchar();
			while(c!='.'&&c!='#'&&c!='A'&&c!='B')c=getchar();
			if(c=='A')ax=i,ay=j;
			if(c=='B')bx=i,by=j;
			if(c=='#')mp[i][j]=1;
		}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			if(!mp[i][j]){
				if(i!=n&&!mp[i+1][j])g[id[i][j]].push_back(id[i+1][j]),g[id[i+1][j]].push_back(id[i][j]);
				if(j!=m&&!mp[i][j+1])g[id[i][j]].push_back(id[i][j+1]),g[id[i][j+1]].push_back(id[i][j]);
			}
	for(int i=1;i<=n*m;++i)
		if(!dfn[i])
			tarjan(i),dfs(i),DFS(i);
	for(int d=0;d<4;++d){
		ci x=bx+fx[d],y=by+fy[d];
		if(x<1||x>n||y<1||y>m||mp[x][y])continue;
		if(!check(id[ax][ay],id[x][y],id[bx][by]))ins(bx,by,d);
	}
	while(!q.empty()){
		ci x=q.front().x,y=q.front().y,d=q.front().d;q.pop();
		for(int d2=0;d2<4;++d2){
			ci xx=x+fx[d2],yy=y+fy[d2];
			if(d==d2||mp[xx][yy]||xx<1||xx>n||yy<1||yy>m)continue;
			if(!check(id[x+fx[d]][y+fy[d]],id[xx][yy],id[x][y]))ins(x,y,d2);
		}
		ci xx=x-fx[d],yy=y-fy[d];
		if(xx<1||xx>n||yy<1||yy>m||mp[xx][yy])continue;
		ins(xx,yy,d);
	}
	for(int x,y;Q;--Q){
		scanf("%d%d",&x,&y);
		if((x==bx&&y==by)||vis[x][y][0]||vis[x][y][1]||vis[x][y][2]||vis[x][y][3])puts("YES");
		else puts("NO");
	}
	return 0;
}