「题解」迷宫 maze

题目链接:GMOJ 6293/改编自Codeforces 413E Maze 2D

题目

题目描述

小奇被困在一个 $N\times M$ 的迷宫中,迷宫的某些格子有着障碍,无法通过。出口在小奇的右方,因此小奇每一步只能向上、右、下三个方向行走。

由于某些神秘力量的作用,小奇和出口的位置会不断改变,同时迷宫的构造也有可能改变。

你要做的就是帮助小奇算出,对于每种情况,小奇最少要走多少步才能到达出口。如果小奇无论怎样都无法走出迷宫,请输出 -1

输入格式

第一行包含三个正整数 $N,M,Q$,分别表示迷宫的行数、列数、以及操作个数。

接下来 $N$ 行,每行 $M$ 个整数,每个整数为 $0$ 或 $1$。如果为 $0$,表示这个格子中存在障碍,无法通行;如果为 $1$,表示这个格子可以通行。

接下来 $Q$ 行,每行第一个整数 $\text{opt}$ 表示操作的类型。

$\text{opt}=1$,接下来会有 $2$ 个整数 $a,b$,表示改变迷宫坐标为 $(a,b)$ 这一格的通行情况,即如果原先可以通行,现在变为无法通行,反之亦然。

$\text{opt}=2$,接下来会有 $4$ 个整数 $a,b,c,d$,表示询问小奇的坐标为 $(a,b)$,出口坐标为 $(c,d)$ 时的答案。

输出格式

对于每个 $\text{opt}=1$,输出一行一个整数,表示小奇到迷宫出口的距离。

样例输入输出

#1

  • Input:
2 3 5
1 1 1
1 1 1
2 2 1 1 2
2 2 2 1 2
1 1 2
2 1 1 2 2
2 2 1 1 2
  • Output:
2
1
2
-1

数据范围

对于 $30\%$ 的数据,$1\leq N\leq 3,1\leq M\leq 5\times 10^3,1\leq Q\leq 5\times 10^3$。

对于 $60\%$ 的数据,$1\leq N\leq 4,1\leq M\leq 10^5,1\leq Q\leq 3\times 10^4$。

变量数据范围
$N$$1\leq N\leq 5$
$M$$1\leq M\leq 2\times 10^5$
$Q$$1\leq Q\leq 5\times 10^4$
$a,c$$1\leq a,c\leq N$

时空限制

题目编号时间限制空间限制
GMOJ 6293$1.5\text{s}$$256\text{MiB}$

题解

本题的解法比较单一,模拟是零分。

解法 A(线段树)

思路

用线段树合并结果。

代码

渐进时间复杂度为 $\Theta(mn^3+Qn^3\log_2m)$。

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::min;
#define INF 0X3F3F3F3F
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    register char ch=getchar();
    register int res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}
const int MAXN=5+1;//空间比较有限
const int MAXM=200000+1;//空间比较有限
struct SegmentTree{
    struct Node{
        int f[MAXN][MAXN];//f[i][j]表示在区间内从第i行走到第j行的距离
        inline void Init(void){
            memset(f,0X3F,sizeof(f));
            return;
        }
    };
    int n;
    bool M[MAXN][MAXM];
    Node unit[MAXM<<2];
    inline void pushup(Node &fa,Node &l,Node &r){
        register int i,j,k;
        fa.Init();
        for(k=1;k<=n;++k)//枚举中间点k
            for(i=1;i<=n;++i)
                for(j=1;j<=n;++j)
                    fa.f[i][j]=min(fa.f[i][j],l.f[i][k]+r.f[k][j]+1);
        return;
    }
    inline void Get(int ID,int l){//得到最小节点(1)的信息
        register int i,j,k;
        unit[ID].Init();//先初始化
        for(i=1;i<=n;++i){
            unit[ID].f[i][i]=(M[i][l]?0:INF);//可不可以走
            if(M[i][l]&&M[i-1][l])//上下联通
                unit[ID].f[i][i-1]=unit[ID].f[i-1][i]=1;
        }
        for(k=1;k<=n;++k)
            for(i=1;i<=n;++i)
                for(j=1;j<=n;++j)
                    unit[ID].f[i][j]=min(unit[ID].f[i][j],unit[ID].f[i][k]+unit[ID].f[k][j]);
        return;
    }
    inline void Build(int ID,int l,int r){
        if(l==r)
            Get(ID,l);
        else{
            register int mid=(l+r)>>1;
            Build(ID<<1,l,mid);
            Build(ID<<1|1,mid+1,r);
            pushup(unit[ID],unit[ID<<1],unit[ID<<1|1]);
        }
        return;
    }
    inline void Update(int ID,int l,int r,int pos){//更新
        if(l==r)
            Get(ID,l);
        else{
            register int mid=(l+r)>>1;
            if(pos<=mid)
                Update(ID<<1,l,mid,pos);
            else
                Update(ID<<1|1,mid+1,r,pos);
            pushup(unit[ID],unit[ID<<1],unit[ID<<1|1]);
        }
        return;
    }
    inline Node Query(int ID,int l,int r,int posl,int posr){//查询
        if(posl==l&&r==posr)
            return unit[ID];
        register int mid=(l+r)>>1;
        if(posr<=mid)
            return Query(ID<<1,l,mid,posl,posr);
        else if(posl>mid)
            return Query(ID<<1|1,mid+1,r,posl,posr);
        else{
            Node
            fa,
            left=Query(ID<<1,l,mid,posl,mid),
            right=Query(ID<<1|1,mid+1,r,mid+1,posr);
            pushup(fa,left,right);
            return fa;
        }
    }
};
int n,m,Q;
SegmentTree::Node ans;
SegmentTree T;
int main(void){
    freopen("maze.in","r",stdin);
    freopen("maze.out","w",stdout);
    register int i,j;
    n=read(),m=read(),Q=read();
    //scanf("%d%d%d",&n,&m,&Q);
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j){
            //static int a;
            //scanf("%d",&a);
            T.M[i][j]=read()/*a*/;
        }
    T.n=n;
    T.Build(1,1,m);
    while(Q--){
        static int opt,a,b,c,d;
        opt=read();
        //scanf("%d",&opt);
        if(opt==1){
            a=read(),b=read();
            //scanf("%d%d",&a,&b);
            T.M[a][b]=!T.M[a][b];
            T.Update(1,1,m,b);
        }
        if(opt==2){
            a=read(),b=read(),c=read(),d=read();
            //scanf("%d%d%d%d",&a,&b,&c,&d);
            if(b>d)//不能向左走
                puts("-1");
            else{
                ans=T.Query(1,1,m,b,d);
                if(ans.f[a][c]<INF)
                    printf("%d\n",ans.f[a][c]);
                else
                    puts("-1");
            }
        }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}