AcWing 1219. 移动距离

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1219. 移动距离原题链接简单

作者：

water-lover , 2020-03-12 20:11:57 , 所有人可见 , 阅读 5559

23

5

题目描述

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

输出样例：

C++代码

#include <bits/stdc++.h>

using namespace std;

int main(){
    int w, m, n;
    cin >> w >> m >> n;
    m --, n --;//序号减1，便于利用公式求行号和列号

    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;
}

21 评论

白吃糖葫芦 2023-04-04 23:07

救命

_chouchou_ 2023-10-26 22:30

我也，救命

mojie123 2022-03-25 13:11

#include<iostream>
using namespace std;
int w,m,n;
int x1,y1,x2,y2;
int main(){
    cin>>w>>m>>n;
    m--,n--;
    x1=m/w,x2=n/w;
    y1=m%w,y2=n%w;
    if((x1&1) ^ (x2&1))y2=w-1-y2;
    cout<<abs(x2-x1)+abs(y2-y1);
    return 0;
}

直接一下搞定，如果不是奇偶交替行，就不管，有一个是就直接随便换一个

晴天. 2023-04-06 18:36

牛

小张张 2021-03-26 10:54

if(x1 & 1) y1 = w - 1 - y1;//特判，是否为奇数行
if(x2 & 1) y2 = w - 1 - y2;
这个语句怎么理解呀？

Unique_8 2021-03-31 14:56

同问，有没有大佬回答一下呀

现代修士o_O 2021-04-07 20:40 回复了 Unique_8 的评论

如果前者是奇数的话，它的二进制最后一位肯定是1 ，偶数就是0。&1 就是把最后一位取出。奇数就为真，反之。

endeavor_1 2021-04-09 22:41 回复了 Unique_8 的评论

因为奇数行的排列是逆向的，通过特判，把逆向变为正向

一抹常规 5天前

跟我一样，嘿嘿

如影随形_6 9个月前

啊？

ww_00 2023-11-04 10:24

妙啊

_chouchou_ 2023-10-26 22:30

救命

不顺我心 2023-04-03 00:08

只能说妙啊，牛

duguruofu 2022-03-02 22:12

ORZ

tocsu 2021-03-20 17:31

直接合起来搞

#include <iostream>

using namespace std;

int main() {
    int w, m, n;
    cin >> w >> m >> n;
    int x1 = (m - 1) / w + 1;
    int x2 = (n - 1) / w + 1;
    int y1 = (x1 & 1) ? ((m - 1) % w + 1) : (w - (m - 1) % w); //如果是奇数
    int y2 = (x2 & 1) ? ((n - 1) % w + 1) : (w - (n - 1) % w);

    cout << abs(x1 - x2) + abs(y1 - y2) << endl; 
    return 0;
}