第六届蓝桥杯算法题解思路及代码：移动距离

妖狐艹你老母 2022-09-30 11:46 40阅读 0赞

## 题目：移动距离 ##

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 两楼间最短移动距离。

例如：  
用户输入：  
6 8 2  
则，程序应该输出：  
4

再例如：  
用户输入：  
4 7 20  
则，程序应该输出：  
5

资源约定：  
峰值内存消耗 < 256M  
CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

注意: main函数需要返回0  
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。  
注意: 所有依赖的函数必须明确地在源文件中 \#include ， 不能通过工程设置而省略常用头文件。

提交时，注意选择所期望的编译器类型。

--------------------

## 思路 ##

思路：将其化为正序，再求行差和列差之和

建立二维数组，他的行数x可以确认：

x = m/w;
        if(m%w != 0){
            x++;
        }

列数为w；  
假设输入是4 7 20

1  2  3  4
    8  7  6  5
    9  10 11 12
    16 15 14 13
    17 18 19 20

将其存入5行4列数组后，查找获得m，n在其中的下标，例如7的下标是i = 1，j = 1 所以正序对应的数字a = i\*w + j + 1 = 6（其正序时的数字）；20的下标为i = 4，j = 3 对应的正序数字b = 20，再求正序数组对应的行差列差之和。

对应的正序数组：

1  2  3  4
    5  6  7  8
    9  10 11 12
    13 14 15 16
    17 18 19 20

此时发现每一层数字和其头上的数字相差都是w（此时w = 4）判断一共几层（上走几步）

//求行差
    while(x >= 1 && a - b > w){
         a = a-w;
         x --;
         c ++; //计数
    }

当其到达同一层时，判断a，b之间的差值，累加上去

c = c + a - b;

## 具体实现代码： ##

#include <iostream>
    #include<math.h>
    
    using namespace std;
    
    int main()
    {
        int w, m, n;
        cin >> w >> m >> n;
        int x, p = 1, q = 0, y, a, b, c = 0;
        //此处注意输入m,n不一定是m大或者n大，所以加个交换
        if(m < n){
            int t;
            t = m;
    
            m = n;
            n = t;
        }
        //获取矩阵的行，列为确定的w
        x = m/w;
        if(m%w != 0){
            x++;
        }
        //申请二维数组并将楼层存入
        int **arr = new int*[x];
        for(int i = 0; i < x; i++){
            arr[i] = new int[w];
        }
    
        for(int i = 0; i < x; i++){
    
            q = p + w - 1;
            y = q;
            for(int j = 0; j < w; j++){
                if(i%2 == 0){
                    arr[i][j] = p;
                    p++;
                }
                else{
                    arr[i][j] = y;
                    y--;
                    p++;
                }
            }
            y = y+w;
        }
        //将m，n在正序矩阵的映射赋值给a，b
        for(int i = 0; i < x; i++){
            for(int j = 0; j < w; j++){
                if(m == arr[i][j]){
                    a = w*i + j + 1;
                }
                if(n == arr[i][j]){
                    b = w*i + j + 1;
    
                }
            }
        }
        //求行差
        while(x >= 1 && a - b > w){
            a = a-w;
            x --;
            c ++;
        }
        //求列差
        c = c + a - b;
        cout << c;
        return 0;
    }