P4082 - Push a Box 题解
经典（？）的推箱子问题。
考虑记录 (箱子的位置, bessie 的位置) 这样的二元组当作状态，正确性肯定是可以的。但是状态是 \((nm)^2\) 这就不好了。但是容易观察到只有当箱子和 bessie 挨在一起的时候的状态才是我们需要关心的关键状态，因为这样才能推得动箱子。你 bessie 要是把箱子放着不动，自己到处游走，那谁管你去了那些景点旅游啊。
接下来要做的事情就是给这 \(4nm\) 个状态之间连边，把它们的连通性确定下来。初始状态显然最多只有 \(4\) 种，对结束位置显然也只有最多 \(4\) 种状态，最终这 \(16\) 对中至少一组连通，那答案就是 YES 否则是 NO。
状态之间的连边只有两种：一种是往当前方向推一格，一种是 bessie 换个方位。前者比较简单，就看看前方有没有障碍物就行了（连的是有向边啊！）。后者的话，判的就是在原图基础上，把箱子的位置堵住（其实就是割掉这个点）然后两种 bessie 的位置是否连通。那这就是圆方树的拿手好戏了——因为把某个点割掉之后原图的分裂情况跟圆方树一致。我们只需要找出 \(4\) 种位置各在哪个儿子树里（或者是割掉的点的子树的补集），枚举一下然后用子树的时间戳区间判就可以了。复杂度是均摊的，不用担心，虽然常数有点大但常数瓶颈不在这里。
上面的后者连边中，并不是 \(4\) 种情况的每一对连通对都要连双向边，如果这样的话最多要连 \(2\dbinom{4}{2}=12\) 条边，平均每个点连出 \(3\) 条。其实可以找到每个连通类，然后用一个有向环连起来，这样每个点连出 \(1\) 条。不难发现结合前者和后者一共要连 \(8nm\) 条边，这大概到了 1e7 级别。而我个人不太喜欢链式前向星那东西，这题一开始也就用 vector 写了。那么被卡空间、卡时间无疑了。把 vector 换成链式前向星立刻就过了，而且跑得很快，使用空间也只有 ML 的一半——STL，尤其是 vector deque 之流，确实是奢侈品。下次要是再在有卡空、卡时风险的图论题里不果断用链式前向星，我就 dlxt 好吧！！（把 vector 换成前向星真的很麻烦，还不如一开始就写）
另外这题有个小坑。如果目的地就是箱子本来在的地方的话，你 bessie 甚至不需要能到达箱子周围。
code（其实 u1s1 链式前向星写的挺清爽的）
#include
using namespace std;
#define pb push_back
const int N=1510;
int n,m,qu;
char a[N][N];
int id(int x,int y){return (x-1)*m+y;}
struct addedge_nei{
int sz,head[N*N],nxt[4*N*N],val[4*N*N];
addedge_nei(){sz=0,memset(head,0,sizeof(head));}
void ae(int x,int y){
sz++,nxt[sz]=head[x],head[x]=sz,val[sz]=y;
}
}nei;
int dfn[2*N*N],low[N*N],nowdfn;
int stk[N*N],top;
int cnt;
struct addedge_cnei{
int sz,head[2*N*N],nxt[4*N*N],val[4*N*N];
addedge_cnei(){sz=0,memset(head,0,sizeof(head));}
void ae(int x,int y){
sz++,nxt[sz]=head[x],head[x]=sz,val[sz]=y;
}
}cnei;
void tar(int x,int fa=0){
stk[top++]=x;
dfn[x]=low[x]=++nowdfn;
if(!fa&&nei.head[x]==0)return cnt++,cnei.ae(n*m+cnt,x),cnei.ae(x,n*m+cnt),void();
for(int i=nei.head[x];i;i=nei.nxt[i]){
int y=nei.val[i];
if(y==fa){fa=-1;continue;}
if(!dfn[y]){
tar(y,x),low[x]=min(low[x],low[y]);
if(dfn[x]<=low[y]){
cnt++;
while(true){
int z=stk[--top];
cnei.ae(n*m+cnt,z),cnei.ae(z,n*m+cnt);
if(z==y)break;
}
cnei.ae(n*m+cnt,x),cnei.ae(x,n*m+cnt);
}
}
else low[x]=min(low[x],dfn[y]);
}
}
int mxdfn[2*N*N];
void dfs(int x,int fa=0){
dfn[x]=mxdfn[x]=++nowdfn;
for(int i=cnei.head[x];i;i=cnei.nxt[i]){
int y=cnei.val[i];
if(y==fa)continue;
dfs(y,x);
mxdfn[x]=mxdfn[y];
}
}
const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
const string str[]={"right","down","left","up"};
int id0(int x,int y){return x*4-y;}
struct addedge_nei0{
int sz,head[4*N*N],nxt[8*N*N],val[8*N*N];
addedge_nei0(){sz=0,memset(head,0,sizeof(head));}
void ae(int x,int y){
sz++,nxt[sz]=head[x],head[x]=sz,val[sz]=y;
}
}nei0;
bool vis0[4*N*N];
void dfs1(int x){
vis0[x]=true;
for(int i=nei0.head[x];i;i=nei0.nxt[i]){
int y=nei0.val[i];
if(!vis0[y])dfs1(y);
}
}
bool ok(int x,int y){return 1<=x&&x<=n&&1<=y&&y<=m&&a[x][y]!='#';}
bool vis[N*N];
void dfs0(int x,int ban){
vis[x]=true;
for(int i=nei.head[x];i;i=nei.nxt[i]){
int y=nei.val[i];
if(!vis[y]&&y!=ban)dfs0(y,ban);
}
}
int main(){
cin>>n>>m>>qu;
for(int i=1;i<=n;i++)scanf("%s",a[i]+1);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i][j]!='#'){
if(i init;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i][j]!='#'){
int x=id(i,j),in[4]={};
for(int k=0;k<4;k++){
int xn=i+dx[k],yn=j+dy[k];
if(!ok(xn,yn)){in[k]=-1;continue;}
if(x==B&&vis[id(xn,yn)])init.pb(id0(x,k));
int now=0;
for(int o=cnei.head[x];o;o=cnei.nxt[o]){
now++;
int y=cnei.val[o];
if(dfn[y] v;
for(int o=0;o<4;o++)if(in[o]==k)v.pb(id0(x,o));
for(int o=0;o+11)nei0.ae(v.back(),v[0]);
}
}
for(int i=0;i