题目描述
资源限制
内存限制:256.0MB C/C++时间限制:1.0s Java时间限制:3.0s Python时间限制:5.0s
————————————————————————————————————————————————————————————————————————————————————————————————————————————
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,
————————————————————————————————————————————————————————————————————————————————————————————————————————————
资源约定:
峰值内存消耗 < 256M
CPU消耗 < 1000ms
样例
输入样例:
6 8 2
输出样例:
4
用户输入:
4 7 20
则,程序应该输出:
5
思想
1 2 3 4 5 6
12 11 10 9 8 7
13 14 15 16 17 18
找规律:
第一行 :1 6
第二行:12( 2*6 ) 7(12 - 7 + 1 =6 - > 7 = 12 + 1 - 6)
第三行:13(12+1 -> (3-1)*6 +1 ) 18(13 + 6 - 1)
奇数行首个元素等于:(行数-1)* 宽度+1 尾元素: 首元素 + 宽度 - 1
偶数行首个元素等于:(行数)* 宽度 尾元素: 首元素 +1 - 宽度
w表示宽度,i表示行数,那么可以列出式子:
偶行: 首 i * w 尾 i*w + 1 - w
奇行: 首(i - 1) * w 尾(i-1) * w + 1 - w
行数 x = i
列数: (尾元素 - 首元素)的绝对值 + 1 : y
C++ 代码
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int x1,y1,x2,y2; // 定义两个点的横纵坐标
int main()
{
int flag1 = 0,flag2 = 0; // 定义标志变量
int w,m,n;
scanf("%d%d%d",&w,&m,&n); // 输入矩形宽度和两个点的坐标
for(int i = 1; i <= 10000; i++) // 枚举矩形的高度
{
// 偶数行
if(i % 2 == 0)
{
// 如果第一个点在这一行,记录横纵坐标并将标志变量flag1设为1
if(m <= i*w && m >= i * w + 1 - w)
{
x1 = i;
y1 = i * w - m + 1;
flag1 = 1;
}
// 如果第二个点在这一行,记录横纵坐标并将标志变量flag2设为1
if(n <= i*w && n >= i * w + 1 - w)
{
x2 = i;
y2 = i * w - n + 1;
flag2 = 1;
}
}
// 奇数行
else{
// 如果第一个点在这一行,记录横纵坐标并将标志变量flag1设为1
if(m >= (i-1)*w + 1 && m <= (i-1)*w + 1 + w -1)
{
x1 = i;
y1 = m - ((i-1)*w + 1) + 1;
flag1 = 1;
}
// 如果第二个点在这一行,记录横纵坐标并将标志变量flag2设为1
if(n >= (i-1)*w + 1 && n <= (i-1)*w + 1 + w -1)
{
x2 = i;
y2 = n - ((i-1)*w + 1) + 1;
flag2 = 1;
}
// 如果两个点都已经找到了,退出循环
if(flag1&&flag2) break;
}
}
printf("%d",abs(x2-x1)+abs(y2-y1));
return 0;
}