题解：AT_abc258_f [ABC258F] Main Street

hyc42_Happiness · 2025-10-22 14:54:41 · 题解

前置

传送门(luogu)

传送门(AT)

题目大意

在平面直角坐标系中，所有直线 x=n 和 y=n（n 为整数）都是道路。其中，直线 x=Bn 和 y=Bn 被称为大通道。

高桥君可以从 (x,y) 移动到相邻的四个点 (x\pm1,y) 或 (x,y\pm1)：

• 如果沿着大通道移动，花费 1 秒；

• 否则花费 K 秒。

求从 (S_x,S_y) 到 (G_x,G_y) 的最短时间。

解题思路

如果不利用大通道，直接曼哈顿距离移动，花费时间为：dis=|S_x−G_x|+|S_y−G_y|,time=dis\times K。

对于起点 (S_x,S_y)，找到它上下左右四个方向最近的大通道：

1. 上方大通道：y=\lceil\frac{S_y}{B}\rceil\times B；
2. 下方大通道：y=\lfloor\frac{S_y}{B}\rfloor\times B；
3. 左方大通道：x=\lfloor\frac{S_x}{B}\rfloor\times B；
4. 右方大通道：x=\lceil\frac{S_x}{B}\rceil\times B。

同样对终点也找到四个方向最近的大通道。

枚举所有可能的组合：

起点连接到哪个大通道（上下左右 4 种）加上终点连接到哪个大通道上下左右 4 种）一共 4\times 4=16 种情况。

对于每种情况：

• 计算从起点到大通道的时间（非大通道部分 \times K）；

• 计算在大通道上移动的时间（大通道部分 \times 1）；

• 计算从大通道到终点的时间（非大通道部分 \times K）。

特殊情况处理

当起点和终点在同一大通道区域时，dis 函数（见 Code）会特殊处理：

• 如果两点都在垂直大通道上且在同一水平区域，可以选择直接垂直移动或绕行；

• 如果两点都在水平大通道上且在同一垂直区域，可以选择直接水平移动或绕行。

dis 函数计算两点在大通道上的最短移动距离，考虑了：

• 直接移动以及绕行（当两点在同一大通道区域时）。

总体复杂度为 O(16\times T)。

Code

int dis(int x1,int y1,int x2,int y2){
    // 两点都在垂直大通道上且在同一水平区域
    if(x1%b==0&&x2%b==0&&y1/b==y2/b)
        return min(abs(x1-x2)+min(y1%b+y2%b,b*2-y1%b-y2%b),abs(y1-y2)+abs(x1-x2)*k);
    // 交换坐标，检查是否都在水平大通道上且在同一垂直区域  
    swap(x1,y1),swap(x2,y2);
    if(x1%b==0&&x2%b==0&&y1/b==y2/b)
        return min(abs(x1-x2)+min(y1%b+y2%b,b*2-y1%b-y2%b),abs(y1-y2)+abs(x1-x2)*k);
    // 一般情况：曼哈顿距离
    return abs(x1-x2)+abs(y1-y2);
}