题解：CF2152B Catching the Krug

___AaAa_bBcCd___ · 2025-10-05 11:40:02 · 题解

题意简述

Doran 和 Krug 在一个网格上玩游戏，网格两维都是编号 0 \sim n。Doran 的移动范围是八连通，Krug 的移动范围是四连通。奇数回合 Krug 可以选择移动一次或不动，偶数回合 Doran 可以选择移动一次或不动。当 Doran 和 Krug 的位置重合时，Doran 就抓到了 Krug。求 Krug 至多能苟多少回合。

题目分析

注意到标签不难发现 Krug 沿一个方向跑到边界一定最优，故考虑分类讨论何时会被抓到。

• 当 Doran 和 Krug 有一维相同时，Doran 一定能保证这维一直相同，且不会影响抓捕。故 Krug 只能沿另一维跑到头然后坐等被抓。此时被抓的条件是 Doran 也跑到了边界，即边界与 Doran 另一维坐标的距离。

• 当两维都不同时，相同的是 Doran 仍然需要到边界才能抓到 Krug。所以 Krug 可以自由选择沿哪一维跑（肯定是 Doran 距离边界较远的那一维），此时因为 Doran 一次能缩短两个维度的距离，所以较大维追上 Krug 时另一维肯定也能追上。

代码实现

#include<bits/stdc++.h>
using namespace std;
int T,n,rk,ck,rd,cd,dx,dy;
int main(){
    cin>>T;
    while(T--){
        cin>>n>>rk>>ck>>rd>>cd;
        if(rk==rd)dx=0;
        else if(rk<rd)dx=rd;
        else dx=n-rd;
        if(ck==cd)dy=0;
        else if(ck<cd)dy=cd;
        else dy=n-cd;
        cout<<max(dx,dy)<<endl;
    }
    return 0;
}