BZOJ2574 Store-Keeper

题目

题目地址

思路

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

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

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

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

分为3种情况讨论：

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

代码

#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