题目

题目地址

思路

仔细分析一下会发现，其实此题的状态数并不多，只有\(100*100*4\)种，人的移动是不需要的，也就是说，我们只需要知道当箱子在某一个位置时，人能不能从箱子的一个侧面走向另一个侧面。

转化成图论模型也就是说，当一个无向图断掉一个点之后，判断两个点的连通性。

这就让人想到了COCI2006/2007 Final的题，这是那道题的一个子问题。

首先用\(Tarjan\)将\(dfs\)树建立出来，处理出每个点的\(low\)值和子树的\(dfs\)序区间，然后,对于\(a\),\(b\)，判断断掉\(x\)之后他们是否联通。

分为3种情况讨论：

1. 两者都不在x的子树内，那么会发现x断掉对这两点的连通性没有什么影响。
2. 两者都在x的子树内，那么只需要将他们跳到x的下面那个点，判断该点的low值是否小于dfn[x]，然，则说明底下存在一条返祖边回到x的上方，在x断掉之后仍然能够使图联通。
3. 两者一个在x的子树内一个不在，这种情况与上面类似，仍然讨论是否存在返祖边使图联通即可。

代码

```c++

include<bits/stdc++.h>

define M 10005

using namespace std;
int n,m,h[M],tt;
char S[105][105];
bool vis[105][105][4];
int dxy[4][2]={1,0,0,1,0,-1,-1,0};
struct edge{int nxt,to;}G[M<<3];
void Add(int a,int b){
G[++tt]=(edge){h[a],b};
h[a]=tt;
}
int dfn[M],low[M],tot,R[M],fa[M][15],dep[M];
int ID(int x,int y){return (x-1)*m+y;}
void Tarjan(int x,int f,int d){
low[x]=dfn[x]=++tot;fa[x][0]=f;dep[x]=d;
for(int i=1;i<=14;i++)
fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=h[x];i;i=G[i].nxt){
int u=G[i].to;
if(u==f)continue;
if(!dfn[u]){
Tarjan(u,x,d+1);
low[x]=min(low[x],low[u]);
}
else low[x]=min(low[x],dfn[u]);
}
R[x]=tot;
}
int Up(int x,int step){
for(int i=14;i>=0;i--)
if(step&1<<i)x=fa[x][i];
return x;
}
struct node{
int x,y,step,fr;
}Q[10005],Q2[40005];
int mark[105][105];int T;
bool check(int x,int y){
return x>=1&&x<=n&&y>=1&&y<=m&&mark[x][y]!=T&&S[x][y]!='S';
}
bool bfs(int sx,int sy,int ex,int ey,int cx,int cy){
int L=0,R=0;
Q[R++]=(node){sx,sy};mark[sx][sy]=T;
while(L!=R){
node e=Q[L++];if(L==10001)L=0;
if(e.x==ex&&e.y==ey){++T;return 1;}
for(int i=0;i<4;i++){
int x=e.x+dxy[i][0];
int y=e.y+dxy[i][1];
if(check(x,y)&&!(x==cx&&y==cy)){
Q[R++]=(node){x,y};
if(R==10001)R=0;
mark[x][y]=T;
}
}
}
++T;
return 0;
}
bool In(int a,int b){
return dfn[a]>=dfn[b]&&dfn[a]<=R[b];
}
bool Ca(int a,int b,int x){
if(!In(a,x)&&!In(b,x))return 1;
if(In