原题链接：移动距离

题目描述

X星球居民小区的楼房全是一样的，并且按矩阵样式排列。

其楼房的编号为 $1,2,3…$

当排满一行时，从下一行相邻的楼往反方向排号。

比如：当小区排号宽度为 $6$ 时，开始情形如下：

1  2  3  4  5  6
12 11 10 9  8  7
13 14 15 .....

我们的问题是：已知了两个楼号 $m$ 和 $n$，需要求出它们之间的最短移动距离（不能斜线方向移动）。

输入格式

输入共一行，包含三个整数 $w,m,n，w$ 为排号宽度，$m,n$ 为待计算的楼号。

输出格式

输出一个整数，表示 $m,n$ 两楼间最短移动距离。

数据范围

$1≤w,m,n≤10000,$

输入样例1：

6 8 2

输出样例1：

4

思路

刚开始我的想法是算出平行和垂直距离，但是总是卡在那个垂直距离算不对，我可能就是蒻吧

这里是求曼哈顿距离 $|x_1 - x_2| + |y_1 - y_2|$ ，所以我们可以求出两点的坐标，直接代公式求出两点的最短距离

首先我们可以先将所有的点 $-1$ 来让点从 $0$ 开始，然后可以看出来，行坐标只需要除以宽度向下取整即可。

列坐标在不考虑翻转的情况下是 $\%w$ ，再考虑翻转的情况。

如果行是奇数行，那么需要对称列坐标 $w - 1 - m \% w$

时间复杂度

$O(1)$

C++ 代码

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

int w, m , n;

int main()
{
    cin >> w >> m >> n;

    m --, n --;
    int x1 = m / w, x2 = n / w;
    int y1 = m % w, y2 = n % w;
    if(x1 & 1) y1 = w - 1 - y1;
    if(x2 & 1) y2 = w - 1 - y2;
    cout << abs(x1 - x2) + abs(y1 - y2) << endl;
    return 0;
}