一个人推箱子,和之前的华容道中的棋子移动有异曲同工之妙,因为每次可以让人走到箱子的其他方向上,或者推一下箱子
所以状态可以设成(f_{i,j,k}),即箱子在((i,j)),人在(k)方向的状态是否存在,一开始也要把人移到箱子旁边作为初始状态,然后每次移动人到箱子其他方位或者推箱子
难点是如何快速判断人是否可以从一个方位移到另一个方位上去.如果可以,说明至少存在一条不经过箱子的路径使得这两个方位联通,那么这两个位置也就是在同一个点双连通分量里面,(tarjan)即可
然后我发现自己一开始并不会求点双
还把转移的一个过程写错了
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define LL long long
#define il inline
#define re register
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define inf 1061109567
using namespace std;
const int N=1500+10,M=N*N*4;
il LL rd()
{
re LL x=0,w=1;re char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int to[M<<1],nt[M<<1],hd[N*N],tot=1;
il void add(int x,int y)
{
++tot,to[tot]=y,nt[tot]=hd[x],hd[x]=tot;
//++tot,to[tot]=x,nt[tot]=hd[y],hd[y]=tot;
}
int mm[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int n,m,qq,sx,sy,ex,ey,id[N][N],nxt[4]={2,3,0,1};
bool a[N][N],f[N][N][4],v[N][N];
int dfn[N*N],low[N*N],st[N*N],tp,ti,cnt;
vector<int> inb[N*N];
void tj(int x,int ffa)
{
dfn[x]=low[x]=++ti,st[++tp]=x;
for(int i=hd[x];i;i=nt[i])
{
int y=to[i];
if(!dfn[y])
{
tj(y,x);
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x])
{
++cnt;
while(tp)
{
int z=st[tp--];
inb[z].push_back(cnt);
if(y==z) break;
}
inb[x].push_back(cnt);
}
}
else if(y!=ffa)low[x]=min(low[x],dfn[y]);
}
}
il bool check(int x,int y)
{
for(int i=0,l1=inb[x].size();i<l1;i++)
for(int j=0,l2=inb[y].size();j<l2;j++)
if(inb[x][i]==inb[y][j]) return true;
return false;
}
struct nnn
{
int x,y,f;
};
int main()
{
n=rd(),m=rd(),qq=rd();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
id[i][j]=(i-1)*m+j;
for(int i=1;i<=n;i++)
{
char cc[N];
scanf("%s",cc+1);
for(int j=1;j<=m;j++)
{
a[i][j]=(cc[j]!='#');
if(cc[j]=='A') ex=i,ey=j;
else if(cc[j]=='B') sx=i,sy=j;
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(!a[i][j]) continue;
for(int k=0;k<4;k++)
if(a[i+mm[k][0]][j+mm[k][1]]) add(id[i][j],id[i+mm[k][0]][j+mm[k][1]]);
}
tj(id[sx][sy],0);
a[sx][sy]=false;
queue<nnn> q;
v[ex][ey]=true;
q.push((nnn){ex,ey,0});
while(!q.empty())
{
int x=q.front().x,y=q.front().y;
q.pop();
for(int j=0;j<4;j++)
{
int xx=x+mm[j][0],yy=y+mm[j][1];
if(!a[xx][yy]||v[xx][yy]) continue;
v[xx][yy]=true;
q.push((nnn){xx,yy,0});
}
}
a[sx][sy]=true;
for(int j=0;j<4;j++)
{
int xx=sx+mm[j][0],yy=sy+mm[j][1];
if(v[xx][yy]&&a[xx][yy]) f[sx][sy][j]=true,q.push((nnn){sx,sy,j});
}
while(!q.empty())
{
int x=q.front().x,y=q.front().y,fx=q.front().f;
q.pop();
for(int j=0;j<4;j++)
{
int xx=x+mm[j][0],yy=y+mm[j][1];
if(j==nxt[fx]&&a[xx][yy]&&!f[xx][yy][fx])
{
f[xx][yy][fx]=true;
q.push((nnn){xx,yy,fx});
}
int bx=x+mm[fx][0],by=y+mm[fx][1];
if(f[x][y][j]||!check(id[bx][by],id[xx][yy])) continue;
f[x][y][j]=true;
q.push((nnn){x,y,j});
}
}
while(qq--)
{
int x=rd(),y=rd();
bool ok=f[x][y][0]|f[x][y][1]|f[x][y][2]|f[x][y][3]|(x==sx&&y==sy);
printf("%s
",ok?"YES":"NO");
}
return 0;
}