题解：CF413E Maze 2D

Polarisx · 2025-05-31 21:35:09 · 个人记录

题目传送门。

思路

由于是 2\times n 的矩阵，因此无需考虑会在操作中同时出现向左走和向右走，那么最优策略就是一直向右走，如果走不通就上下移动，横向移动的步数是固定的，因此我们只需考虑上下移动的次数，不妨将上下两段划分出联通块，接着依据连通块之间的连通性建出一颗树，现在我们只需求出查询中 x,y 所在连通块在树上的距离即可。

由于树的特殊性（由一条主链和若干个度数为 1 的点组成），那么我们可以 \mathcal O(1) 计算两个点的距离。

时间复杂度 \mathcal O(n)。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int Maxn=1e6+6;
int n,Q;
int a[3][Maxn];
int bel[3][Maxn],deg[Maxn],dep[Maxn],col[Maxn],fa[Maxn],dfn[Maxn],sz[Maxn];
int tot=1,cnt,op;

vector<int>e[Maxn];

void dfs(int u,int ft){
    dfn[u]=++op; sz[u]=1;
    dep[u]=dep[ft]+1; col[u]=cnt; fa[u]=ft;
    for(auto v:e[u]){
        if(v==ft) continue;
        dfs(v,u); sz[u]+=sz[v];
    }
}

int main(){
    scanf("%d%d",&n,&Q);
    for(int i=1;i<=2;i++)
        for(int j=1;j<=n;j++){
            char c; cin>>c;
            a[i][j]=(c=='X');
        }
    for(int i=1;i<=2;i++){
        for(int j=1;j<=n;j++){
            if(a[i][j]){
                ++tot; continue;
            }
            bel[i][j]=tot;
        }
        ++tot;
    }

    bel[2][n+1]=1e9;
    for(int i=1;i<=n;i++){
        int j=i;
        while(!a[1][j] and j<=n) ++j; --j;
        if(j<i) continue;
        int l=i,r=j;
        while(a[2][l] and l<=n) ++l;
        while(a[2][r] and r>=1) --r;
        for(int k=max(bel[2][l],1);k<=bel[2][r];k++){
            e[bel[1][i]].emplace_back(k);
            e[k].emplace_back(bel[1][i]);
            deg[k]++, deg[bel[1][i]]++;
        }
        i=j;
    }

    for(int i=1;i<=tot;i++) if(!dep[i]) ++cnt,dfs(i,0);

    while(Q--){
        int x,y;
        scanf("%d%d",&x,&y);
        int p=x;

        int l=abs((x-1)%n-(y-1)%n);
        x=bel[(x-1)/n+1][(x-1)%n+1];
        y=bel[(y-1)/n+1][(y-1)%n+1];
        if(col[x]!=col[y]){
            puts("-1");
            continue;
        }
        int d=abs(dep[fa[x]]-dep[fa[y]])+2;
        if(dfn[x]>dfn[y]) swap(x,y);
        if(dfn[x]<=dfn[y] and dfn[y]<dfn[x]+sz[x]) d-=2;

        printf("%d\n",d+l);
    }

    return 0;
}