1219. 移动距离 题解

跳转链接 ​

https://www.acwing.com/problem/content/1221/

题目描述 ​

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

输入样例 6 8 2 输出样例 4

题解思路 ​

显然易见，最短距离即是它们的曼哈顿距离,即|x1 - x2| + |y1 - y2| 对于给出的m, n,通过-1的方式来使得求出行号、列号更方便 并且先以正常的顺序给出二维数组 比如当w = 6, m = 6, n = 5时 原先是

  |  1  2  3  4  5  6  行
--+-------------------
 1|  1  2  3  4  5  6
 2|  7  8  9  10 11 12
 3| 13 14 15 16...
列

通过一般公式：行号 = x / w, 列号 = x % w; m所在行就是6/6 = 第1行,n所在行就是5/6 = 第0行 m所在列就是6%6 = 第0列,n所在列就是5%6 = 第5列 但是m和n是在同一行的,显然不符合

通过减1后变为

  | 0  1  2  3  4  5  行
--+-------------------
 0|  0  1  2  3   4   5
 1|  6  7  8  9  10  11
 2| 12 13 14 15 .....
列

m所在行就是5/6 = 第1行,n所在行就是4/6 = 第0行 m所在列就是5%6 = 第5列,n所在列就是4%6 = 第4列 显然更符合一般公式,所以将所有的数-1;

接下来将正常情况的数组变成题目要求的数组,即奇数行翻转 由分析可以得出翻转后只改变m, n的列号,不改变m, n的行号 得出公式翻转后的列号 = w - 1 - 原先的列号

例子:翻转前：	          翻转后：
6 7 8 9 10 11             11 10 9 8 7 6
翻转前7的列号是1	          翻转后7的列号是4
4(翻转后的列号) = 6(w) - 1 - 1(原先的列号)

代码 ​

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int w, m, n;
    cin >> w >> m >> n;
    m --, n --;
    
    int x1 = m / w, y1 = m % w;
    int x2 = n / w, y2 = n % w;
 
    if(x1 & 1)  y1 = w - 1 - y1;  //如果是奇数行，就转换y1为正常排列翻转后的列号
    if(x2 & 1)  y2 = w - 1 - y2;
    
    cout << abs(x1 - x2) + abs(y1 - y2);   //最短距离即曼哈顿顿距离
    return 0;
}