【牛客4581题解析】圆桌路径优化：曼哈顿距离与半径限制的解题策略

一、题目解读

牛客4581题要求计算在圆桌上从坐标(x1, y1)到(x2, y2)的最少移动步数。题目中，圆桌的半径为r，移动需沿曼哈顿路径（即仅横向或纵向移动），且路径需考虑圆桌边缘的环绕效果。需结合几何距离与圆桌特性，设计优化算法。

二、解题思路

采用“分情况讨论+曼哈顿距离优化”策略：

1. 计算两点间的曼哈顿距离（dx=|x1-x2|, dy=|y1-y2|）；

2. 根据dx、dy特征分三类情况：

    同点：步数为0；

    单轴移动：利用圆桌环绕特性，通过数学推导调整步数（如dx=0时，dy步数需适配半径）；

    双轴移动：取两轴调整步数的最大值，确保路径最短。

    核心在于将几何距离与圆桌半径限制转化为数学表达式，避免复杂模拟。

三、解题步骤

1. 输入解析：读取半径r及坐标(x1, y1, x2, y2)。

2. 曼哈顿距离计算：通过abs函数获取dx、dy。

3. 分情况处理：

    同点：直接输出0；

    单轴：计算调整后的步数（如dy轴移动时，公式为(dy+2r-1)/(2r)）；

    双轴：取两轴公式结果的最大值。

4. 输出优化步数。

步骤简洁，逻辑清晰，避免冗余计算。

四、代码与注释

#include <iostream>  
#include <cmath>  
using namespace std;  

int main() {  
    int r, x1, y1, x2, y2;  
    while(cin >> r >> x1 >> y1 >> x2 >> y2){  
        // 计算中心点之间的曼哈顿距离  
        int dx = abs(x1 - x2);  
        int dy = abs(y1 - y2);  

        // 基本移动步数  
        int steps = dx + dy;  

        // 处理圆桌半径限制  
        if (dx == 0 && dy == 0) {  
            cout << 0 << endl;  
        } else if (dx == 0) {  
            // 仅y轴移动，利用半径调整步数公式  
            cout << (dy + 2*r - 1) / (2*r) << endl;  
        } else if (dy == 0) {  
            // 仅x轴移动，同理调整  
            cout << (dx + 2*r - 1) / (2*r) << endl;  
        } else {  
            // 双轴移动，取两方向调整后的最大值  
            cout << max((dx + 2*r - 1)/(2*r), (dy + 2*r - 1)/(2*r)) << endl;  
        }  
    }  
    return 0;  
}

五、总结

本题解题关键在于将曼哈顿距离与圆桌环绕特性结合，通过数学公式简化路径计算。需注意边界条件（如两点重合）及单/双轴移动的不同处理逻辑。代码实现简洁高效，适用于类似几何路径优化问题。未来可拓展至三维或更复杂约束场景