题解

思路分析

这是一道 BFS + Tarjan + DFS 的综合图论问题，需要判断推箱子的可达性。

问题建模

• Bessie 在网格中推动箱子
• 箱子被推时，Bessie 必须站在箱子的对侧
• 判断箱子能否被推到指定位置

核心思路

1. 状态定义

状态需要包含：

• 箱子的位置 $(x_B, y_B)$
• Bessie 相对箱子的方向（4个方向）

这样状态数为 $O(N \times M \times 4)$。

2. Tarjan 找强连通分量

对于 Bessie 能到达的区域，使用 Tarjan 算法找强连通分量，判断 Bessie 能否绕到箱子的不同侧面。

3. BFS 预处理可达性

从 Bessie 起始位置 BFS，判断她能否到达箱子位置。

4. DFS 搜索箱子状态

定义 $ans[x][y][dir]$ 表示箱子在 $(x, y)$，Bessie 在 $dir$ 方向能否到达。

状态转移：

• 如果 Bessie 能在当前方向推箱子，更新箱子的新位置
• 如果 Bessie 能绕到箱子的其他侧（在强连通分量内），更新方向

算法步骤

1. BFS 判断初始可达：

   • 从 Bessie 起点 BFS
   • 找到能到达箱子的初始位置

2. Tarjan 求 SCC：

   • 对 Bessie 可达区域求强连通分量
   • 预处理 8 个方向的可达关系

3. DFS 枚举箱子状态：

   • 从初始状态开始 DFS
   • 枚举推箱子和绕行的所有可能
   • 标记所有可达的箱子位置

4. 回答询问：

   • 对于每个询问 $(r, c)$
   • 检查 $ans[r][c][0..3]$ 是否有一个为真

复杂度分析

• BFS：$O(NM)$
• Tarjan：$O(NM)$
• DFS：$O(NM \times 4)$
• 总时间复杂度：$O(NM)$
• 空间复杂度：$O(NM)$

#include<bits/stdc++.h>
using namespace std;
int n, m, q, head, tail;         // 谷仓行列数、询问数、队列指针
int xa, ya, xb, yb;             // Bessie和木箱的初始位置
int sx, sy;                     // Bessie在木箱后方的位置
int dl[2500000][2];             // BFS队列，存储坐标
char c[1505][1505];             // 谷仓网格布局
// 四个方向偏移量(上下左右)
int pyx[4] = {1, 0, -1, 0};
int pyy[4] = {0, 1, 0, -1};
// 八个方向偏移量，用于状态转移
int px[8] = {2, 1, 0, -1, -2, -1, 0, 1};
int py[8] = {0, 1, 2, 1, 0, -1, -2, -1};
int dfn[1505][1505], low[1505][1505]; // Tarjan算法时间戳
int st[2500000][2], top;              // 栈，用于Tarjan算法
bool bfs[1505][1505];                // BFS访问标记
bool ok[1505][1505][8];              // 记录八方向可达状态
bool ans[1505][1505][4];             // 记录目标位置是否可达
bool b[1505][1505];                  // 临时标记数组
// Tarjan算法寻找强连通分量
void trj(int nx, int ny) {
    dfn[nx][ny] = low[nx][ny] = ++dfn[0][0]; // 初始化时间戳
    st[++top][0] = nx; st[top][1] = ny;      // 当前节点入栈
    int t = top;   
    for (int i = 0; i < 4; i++) {           // 遍历四个方向
        int tx = nx + pyx[i];
        int ty = ny + pyy[i];        
        // 边界检查和干草格子判断
        if (tx <= 0 || tx > n || ty <= 0 || ty > m) continue;
        if (c[tx][ty] == '#') continue;        
        if (!dfn[tx][ty]) {                 // 未访问过的节点
            int km = top;
            trj(tx, ty);                    // 递归处理子节点
            low[nx][ny] = min(low[nx][ny], low[tx][ty]); // 更新最小时间戳           
            // 发现强连通分量
            if (low[tx][ty] >= dfn[nx][ny]) {
                b[nx][ny] = 1;
                for (int j = km + 1; j <= top; j++) { // 标记强连通分量节点
                    int tnx = st[j][0];
                    int tny = st[j][1];
                    b[tnx][tny] = 1;                   
                    // 标记八邻域的可达关系
                    for (int k = 0; k < 8; k++) {
                        int ttx = tnx + px[k];
                        int tty = tny + py[k];
                        
                        // 边界检查和可达性判断
                        if (ttx <= 0 || ttx > n || tty <= 0 || tty > m) continue;
                        if (!b[ttx][tty]) continue;
                        
                        // 记录双向可达关系
                        ok[tnx][tny][k] = 1;
                        ok[ttx][tty][(k + 4) % 8] = 1;
                    }
                }                
                // 重置标记，回溯
                for (int j = km + 1; j <= top; j++) 
                    b[st[j][0]][st[j][1]] = 0;
                b[nx][ny] = 0;
                top = km; // 恢复栈状态
            }
        } else {
            // 处理已访问节点，更新最小时间戳
            low[nx][ny] = min(low[nx][ny], dfn[tx][ty]);
        }
    }
}
// 深度优先搜索标记可达状态
void dfs(int nx, int ny, int nt) {
    if (ans[nx][ny][nt]) return; // 已访问过的状态
    ans[nx][ny][nt] = 1;         // 标记当前状态为可达
    int tx = nx + pyx[nt];       // 向nt方向移动
    int ty = ny + pyy[nt];
    // 检查边界和干草，继续搜索
    if (!(tx <= 0 || tx > n || ty <= 0 || ty > m || c[tx][ty] == '#'))dfs(tx, ty, nt);
    int rx = nx - pyx[nt];       // 木箱的后方位置
    int ry = ny - pyy[nt];
    // 遍历八个方向，进行状态转移
    for (int i = 0; i < 8; i++) {
        if (ok[rx][ry][i] && px[i] * pyx[nt] + py[i] * pyy[nt] > 0)
            dfs(nx, ny, (i - nt + 2) % 4);
    }
}
int main() {
    scanf("%d%d%d", &n, &m, &q); // 读取谷仓行列数和询问数
    // 读取谷仓布局并记录初始位置
    for (int i = 1; i <= n; i++) {
        scanf("%s", c[i] + 1);
        for (int j = 1; j <= m; j++) {
            if (c[i][j] == 'A') xa = i, ya = j; // Bessie初始位置
            if (c[i][j] == 'B') xb = i, yb = j; // 木箱初始位置
        }
    }
    trj(xa, ya); // 分析Bessie可达区域的强连通分量
    // BFS寻找Bessie到木箱的路径
    dl[++tail][0] = xa; dl[tail][1] = ya;
    bfs[xa][ya] = 1;
    while (head < tail) {
        int nx = dl[++head][0];
        int ny = dl[head][1];
        for (int i = 0; i < 4; i++) {
            int tx = nx + pyx[i];
            int ty = ny + pyy[i];
            // 边界检查、干草检查和访问标记检查
            if (tx <= 0 || tx > n || ty <= 0 || ty > m) continue;
            if (c[tx][ty] == '#') continue;
            if (bfs[tx][ty]) continue;
            dl[++tail][0] = tx; dl[tail][1] = ty;
            bfs[tx][ty] = 1;
            // 找到木箱位置，记录Bessie在木箱后方的位置
            if (tx == xb && ty == yb) {
                sx = nx;
                sy = ny;
            }
        }
	}
    // 处理Bessie无法到达木箱的情况
    if (sx == 0 && sy == 0) {
        for (int i = 1; i <= q; i++) {
            int x, y;
            scanf("%d%d", &x, &y);
            if (x == xb && y == yb) printf("YES\n");
            else printf("NO\n");    
        }
        return 0;
    }
    // 确定初始推动方向并开始DFS
    for (int i = 0; i < 4; i++)
        if (sx + pyx[i] == xb && sy + pyy[i] == yb)dfs(xb, yb, i);
    // 处理所有询问
    for (int i = 1; i <= q; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (ans[x][y][0] || ans[x][y][1] || ans[x][y][2] || ans[x][y][3])
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

题解

思路分析

「推箱子」的离线判定问题。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;
}