2015年第六届蓝桥杯省赛-H. 移动距离

2021-12-16 · 64次阅读 · 原创 · 数据结构与算法

#蓝桥杯 #题解 #数学

原题链接

题面

X 星球居民小区的楼房全是一样的，并且按矩阵样式排列。其楼房的编号为 1,2,3,⋯

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

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

1 2 3 4 5 6

12 11 10 9 8 7

13 14 15 ⋯

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

输入描述

输入为 3 个整数 w,m,n，空格分开，都在 1 到 10000 范围内，w为排号宽度，m,n 为待计算的楼号。

输出描述

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

输入样例 1

6 2 8

输出样例 1

输入样例 2

4 7 20

输出样例 2

题解

数学

将两个点的位置的坐标找出来，直接求其哈密顿距离（即A(x1, y1)，B(x2, y2)，则 $dist(A, B) = |x_1 - x_2| + |y_1 - y_2|$ ）即可。具体描述见代码。

代码

#include<iostream>

using namespace std;

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

    int mr, mc, nr, nc;
    mr = (m % w == 0 ? m / w : (m / w + 1));    //m所在行数
    nr = (n % w == 0 ? n / w : (n / w + 1));    //n所在行数

    //计算m所在列即mc
    if (mr % 2 == 0) {  //偶数行，从右向左
        int x = m - (mr - 1) * w;
        mc = w - x + 1;
    } else {            //奇数行，从左往右
        mc = m - (mr - 1) * w;
    }

    //计算n所在列即nc
    if (nr % 2 == 0) {  //偶数行，从右向左
        int x = n - (nr - 1) * w;
        nc = w - x + 1;
    } else {            //奇数行，从左往右
        nc = n - (nr - 1) * w;
    }

    int res = abs(mr - nr) + abs(mc - nc);
    cout << res << endl;

    return 0;
}

标题：	2015年第六届蓝桥杯省赛-H. 移动距离
链接：	https://www.fightingok.cn/detail/177
更新：	2022-09-18 22:45:40
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可