OJ刷题记录：问题 A: 蓝桥杯(C/C++组)2015-8 移动距离

问题 A: 蓝桥杯(C/C++组)2015-8 移动距离

题目要求： 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 两楼间最短移动距离。

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

解题思路： 根据题目的描述，我们可知 X 星球的居民小区排列成一个以 w 为列的矩阵，要求两个楼房间的最短路径，即求矩阵中的两点之间的最短路径，而矩阵中的两点围成的矩形的长宽和就是两点之间的最短路径，在不确定两个点的位置的情况下，我们分别取两个点的横纵坐标差的绝对值，相加，便是两点之间的最短路径。 本题关键点在于这个矩阵的偶数行（假设矩阵的第一行下标为 1 ），按照题目要求，矩阵偶数行的元素次序是正常数字顺序的逆序。我们需要在取列坐标 y 时进行另外的判断和转换。

以下代码有些冗长，可以写得更精简。

通关代码：

#include <iostream>
#include <algorithm>

using namespace std;

struct Pos {
	int _x;
	int _y;
	Pos(int x, int y):_x(x), _y(y) {}
};

Pos getPos(int w, int num) {
	int x, y;
	
	if (num % w == 0) {
		x = num / w;
	} else {
		x = (num + w) / w;
	}
	
	if (x % 2 == 0) {
		y = w - (num % w) + 1;
	} else {
		y = num % w ? num % w : w;
	}
	
	return Pos(x, y);
}

int main() {
	int w, m, n, res;
	
	cin >> w >> m >> n;
	
	Pos M = getPos(w, m);
	Pos N = getPos(w, n);
	
	res = abs(M._x - N._x) + abs(M._y - N._y);
	
	cout << res;
	
	return 0;
}

毕。