蓝桥杯蛇形矩阵曼哈顿距离计算解析

1. 问题背景与理解

这道题目来自蓝桥杯2015年省赛B组的H题，考察的是数学计算和逻辑思维能力。题目描述了一个X星球居民小区的特殊楼房排列方式，要求我们计算两个楼号之间的最短移动距离。

1.1 题目核心理解

题目给出了三个关键信息：

1. 楼房按矩阵样式排列，编号从1开始递增
2. 当排满一行时，下一行的排列方向与上一行相反（蛇形排列）
3. 移动只能水平或垂直方向，不能斜向移动（即曼哈顿距离）

举个例子，当排号宽度w=6时，楼房的排列如下：

code复制1  2  3  4  5  6
12 11 10 9  8  7
13 14 15 16 17 18
24 23 22 21 20 19
...

1.2 问题转化

我们需要解决的问题可以分解为：

1. 给定楼号m和n，确定它们在矩阵中的坐标位置(x1,y1)和(x2,y2)
2. 计算这两个坐标之间的曼哈顿距离：|x1-x2| + |y1-y2|

关键在于如何将楼号转换为矩阵坐标，特别是要考虑蛇形排列的特殊性。

2. 解题思路分析

2.1 坐标计算原理

对于常规的矩阵排列（从左到右顺序排列），我们可以很容易地计算出坐标：

• 行号x = (n-1) // w
• 列号y = (n-1) % w

但对于蛇形排列，奇数行（从0开始计数）需要反向计算列号。具体来说：

1. 计算原始行号x = (n-1) // w
2. 计算原始列号y = (n-1) % w
3. 如果x是奇数（从0开始计数），则需要反转列号：y = w - y - 1

2.2 曼哈顿距离计算

曼哈顿距离（也称为出租车距离或L1距离）是指在网格中两点之间沿着网格线行走的最短距离。计算公式为：
distance = |x1 - x2| + |y1 - y2|

这个距离计算不考虑对角线移动，完全符合题目"不能斜线方向移动"的要求。

3. 代码实现详解

让我们仔细分析提供的AC代码，理解每个部分的实现逻辑。

3.1 代码结构解析

c复制#include <stdio.h>
#include <stdlib.h>

int main()
{
    int w, m, n;
    while (~scanf("%d%d%d", &w, &m, &n)) {