题解：P13096 [FJCPC 2025] 难以控制的滑板火箭

HPXXZYY · 2025-10-12 16:25:15 · 题解

给定一张图，1 表示可以到达，0 表示障碍。你一次移动可以向相邻八个方向运动，但不能碰到障碍物。单位时间内你可以且进行 [l,r] 次移动（在区间内即可，具体多少次可以选择）。

求从 (1,1) 到 (n,m) 需要的最少时间，注意必须在进行完单位时间内所有移动后停留在 (n,m) 才算到达。

第一眼，肯定和 bfs 求最短路有关。假设最短路长度是 L。

第二眼，时间最短肯定开始阶段都进行 r 次操作。

所以答案就是 \left \lceil \frac{L}{r} \right \rceil？当然不是。

不过这个肯定是答案的下界，我们考虑一下什么情况下可以达到这个下界。

首先，如果 L 恰好是 r 的倍数当然就是这个答案，这种情况太平凡。下面都假设 L 不是 r 的倍数。

设 \text{tmp}=\left \lceil \frac{L}{r} \right \rceil。由于 L 不是 r 的倍数，因此如果在 \text{tmp} 的时间内每步都移动 r 次肯定会出现的这样的情况：在 \text{tmp} 时间的某次移动到达了终点，但是后续还需要进行移动。

怎么消耗掉这些多余的步骤呢？一个最简单的方法就是在终点和终点前一点反复横跳，这样一轮操作会消耗掉 2 次多余的移动。也就是说，通过这种反复横跳的操作可以是移动步数变成任何大于等于 L 且与 L 奇偶相同的数。

当然，如果 \text{tmp}\times r 和 L 同奇偶，那么答案还是下界 \text{tmp} 不变。这是答案取下界的又一种情况。

如果 \text{tmp}\times r 和 L 奇偶相反，但 l \not = r，那么在第 \text{tmp} 时间内只移动 (r-1) 步是一定合法的。而 (\text{tmp}\times r-1) 和 L 是同奇偶的。因此 l\not = r 时依然取下界。

接下来只剩一种情况了，就是 l=r 且 \text{tmp}\times r 与 L 奇偶不同。

1. 通过分层图的方法求出奇偶最短路的长度。
2. 如果 l \not = r，答案就是下界。
3. 如果 l = r。判断 l 的奇偶性。如果 l 为偶数，考虑偶数最短路至少加几个 2 可以变成 r 的倍数。其实稍微思考可以发现，也就是下界。如果 l 是奇数，则分别判断奇最短路和偶最短路。

注意到 l=r 且都为奇数时，假设某最短路长度为 d，那么答案要么是 \left \lfloor \frac{d}{r} \right \rfloor（d 恰好为 r 的倍数），要么是它加 1，要么是它加 2。加 1 还是加 2 取决于 d 和 \left ( \left \lfloor \frac{d}{r} \right \rfloor +1 \right )l 的奇偶是否相同。

考虑到 l 是偶数，也就是 d 和 \left \lfloor \frac{d}{r} \right \rfloor 的奇偶是否相同。

const int N=1010;
const int inf=0x3f3f3f3f;

int dis[N][N][2];
bool vis[N][N][2];
int n,m,a[N][N],l,r,ans;

const int dx[]={0,0,-1,-1,-1,1,1,1};
const int dy[]={1,-1,0,1,-1,0,-1,1};

queue<int> q;

void bfs(int s,int t){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            dis[i][j][0]=dis[i][j][1]=inf;
            vis[i][j][0]=vis[i][j][1]=false;
        }

    while (!q.empty()) q.pop();

    q.push(s);q.push(t);q.push(0);
    dis[s][t][0]=0;
    vis[s][t][0]=true;

    while (!q.empty()){
        int u=q.front();q.pop();
        int v=q.front();q.pop();
        int d=q.front();q.pop();

        for(int i=0;i<8;i++){
            int x=u+dx[i],y=v+dy[i];

            if (x<1||x>n||y<1||y>m) continue;

            if (!vis[x][y][!d]&&a[x][y]){
                vis[x][y][!d]=true;
                dis[x][y][!d]=dis[u][v][d]+1;

                q.push(x);
                q.push(y);
                q.push(!d); 
            }
        }
    }
}//分层图最短路

int OZDY(){
    scanf("%d%d",&n,&m);
    scanf("%d%d",&l,&r);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%1d",&a[i][j]);

    bfs(1,1);

    int u=dis[n][m][0],v=dis[n][m][1];
    if (l!=r){
        if (u==inf&&v==inf) printf("-1\n");//无解
        else printf("%d\n",(min(u,v)+r-1)/r);
    }
    else{
        if (l&1){
            if (u==inf&&v==inf) puts("-1");
            else{
                ans=inf; 
                if (u!=inf){
                    int tmp=u/l;
                    if (u%l==0) ;
                    else if (u%2==tmp%2) tmp+=2;
                    else tmp++;

                    ans=min(ans,tmp);
                }//偶最短路
                if (v!=inf){
                    int tmp=v/l;
                    if (v%l==0) ;
                    else if (v%2==tmp%2) tmp+=2;
                    else tmp++;

                    ans=min(ans,tmp);
                }//奇最短路，两种的处理完全对称

                printf("%d\n",ans);
            }
        }
        else{
            if (u==inf) puts("-1");
            else printf("%d\n",(u+r-1)/r);
        }//l 为偶数，其倍数也必然是偶数，只需考虑偶最短路
    }

    return 0;
}