一个人推箱子,和之前的中的棋子移动有异曲同工之妙,因为每次可以让人走到箱子的其他方向上,或者推一下箱子

所以状态可以设成\(f_{i,j,k}\),即箱子在\((i,j)\),人在\(k\)方向的状态是否存在,一开始也要把人移到箱子旁边作为初始状态,然后每次移动人到箱子其他方位或者推箱子

难点是如何快速判断人是否可以从一个方位移到另一个方位上去.如果可以,说明至少存在一条不经过箱子的路径使得这两个方位联通,那么这两个位置也就是在同一个点双连通分量里面,\(tarjan\)即可

然后我发现自己一开始并不会求点双

还把转移的一个过程写错了

// luogu-judger-enable-o2#include
    
     #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 1061109567using 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
     
       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
      
        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\n",ok?"YES":"NO");    }  return 0;}