深入理解与计算二维数组中的曼哈顿距离：从原理到代码实现

2026-02-07 23:23:58 0条评论 5次阅读 0人点赞

在处理二维网格、地图路径规划或游戏开发中的网格移动问题时，我们经常需要计算两个位置之间的距离。虽然我们熟知直线距离（欧几里得距离），但在很多实际场景中，特别是在只能进行水平和垂直移动的网格世界里，“曼哈顿距离”才是真正有意义的度量标准。在这篇文章中，我们将深入探讨什么是曼哈顿距离，为什么它如此重要，以及如何通过多种编程语言高效地计算它。

什么是曼哈顿距离？

让我们先从直观的概念入手。想象一下，你身处一个像纽约曼哈顿那样的城市街道网格中。建筑物呈方块状排列，街道要么是南北向，要么是东西向。如果你想从点 A 到达点 B，你不能像鸟一样直接飞过去（即走直线），你必须沿着街道走。这意味着你只能向东、西、北或南移动。

在这种情况下，两点之间的最短路径长度，就是它们坐标差绝对值的之和。

数学定义：

在二维平面上，给定两个点 $P1(x1, y1)$ 和 $P2(x2, y2)$，曼哈顿距离的计算公式为：

$$ D =

x1 – x2

+

y1 – y2

$$

简单来说，就是“横向距离加上纵向距离”。

问题陈述

场景：

假设我们有一个大小为 $M \times N$ 的二维数组（可以想象为一个棋盘或地图网格）。数组中的每一个单元格都可以通过其行索引和列索引来定位。

输入：

  • 数组的尺寸 $M$（行数）和 $N$（列数）。注意：虽然这两个参数定义了边界，但在计算距离的公式中并不直接参与运算，它们主要用于定义问题空间的范围。
  • 两个点的坐标：

* 点 1: $(X1, Y1)$，其中 $X1$ 是行号，$Y1$ 是列号。

* 点 2: $(X2, Y2)$，其中 $X2$ 是行号，$Y2$ 是列号。

任务：

计算这两个点之间的曼哈顿距离。

示例分析

让我们通过几个具体的例子来加深理解。

示例 1：

  • 输入: $M = 5, N = 5, X1 = 1, Y1 = 2, X2 = 3, Y2 = 3$
  • 计算过程:

* 行方向的距离：$

1 – 3

= 2$

* 列方向的距离：$

2 – 3

= 1$

* 总距离：$2 + 1 = 3$

  • 输出: 3

这意味从 $(1, 2)$ 走到 $(3, 3)$，你需要至少走 3 步（例如：向下走 2 步，向右走 1 步）。

示例 2：

  • 输入: $M = 5, N = 5, X1 = 4, Y1 = 2, X2 = 4, Y2 = 2$
  • 计算过程:

* 行方向的距离：$

4 – 4

= 0$

* 列方向的距离：$

2 – 2

= 0$

* 总距离：$0 + 0 = 0$

  • 输出: 0

这两个点位于同一个位置，所以距离为 0。

核心算法与思路

这个问题的解决方案基于纯粹的数学观察，非常高效。

  • 绝对值： 我们使用绝对值是因为距离总是非负的。无论点 A 在点 B 的左边还是右边，它们之间的“跨度”总是正值。
  • 加法： 在曼哈顿几何中，我们分别在 X 轴和 Y 轴上累加移动的代价。
  • 时间复杂度： 由于这只是两次减法、两次绝对值运算和一次加法，时间复杂度是 O(1)。这是一个常数时间的操作，无论网格多大，计算速度都一样快。
  • 空间复杂度： 我们不需要额外的存储空间（除了存储变量的寄存器），所以辅助空间是 O(1)。

代码实现与详细解析

为了让你能够在实际项目中灵活运用，我们将使用 C++、Java、Python3、C# 和 JavaScript 五种主流语言来实现这个逻辑。我们会特别注意代码的注释和变量命名，使其具有自解释性。

1. C++ 实现

C++ 以其高性能著称，特别是在处理底层数学运算时。这里我们使用了 INLINECODEdc43a466 库中的 INLINECODE6564028e 函数。

// C++ 代码实现：计算二维数组中两点间的曼哈顿距离
#include 
#include  // 引入数学库以使用绝对值函数
using namespace std;

/*
 * 函数：manhattanDist
 * 功能：计算两点 的曼哈顿距离
 * 参数：M, N - 网格的尺寸（虽未在计算中直接使用，但保留作为环境参数）
 *       X1, Y1 - 第一个点的坐标
 *       X2, Y2 - 第二个点的坐标
 * 返回值：曼哈顿距离（整数）
 */
int manhattanDist(int M, int N, int X1, 
                  int Y1, int X2, int Y2)
{
    // 核心公式：行坐标之差的绝对值 + 列坐标之差的绝对值
    int dist = abs(X2 - X1) + abs(Y2 - Y1);
    return dist;
}

// 主驱动代码
int main()
{
    // 定义二维数组的环境大小（5行5列）
    int M = 5, N = 5;

    // 定义第一个点 (X1, Y1) -> 第2行，第3列（索引从1开始演示）
    int X1 = 1, Y1 = 2;

    // 定义第二个点 (X2, Y2) -> 第4行，第4列
    int X2 = 3, Y2 = 3;

    // 调用函数并输出结果
    cout << "点 (" << X1 << "," << Y1 << ") 和 点 (" << X2 << "," << Y2 << ") 之间的曼哈顿距离是: ";
    cout << manhattanDist(M, N, X1, Y1, X2, Y2) << endl;
    
    return 0;
}

2. Java 实现

Java 是企业级开发的首选，其 INLINECODE3025c468 类提供了完善的数学运算支持。注意在 Java 中处理整数时，我们使用 INLINECODE750854a5。

// Java 代码实现：计算二维数组中两点间的曼哈顿距离

class ManhattanDistance {

    /**
     * 计算曼哈顿距离的静态方法
     * @param M 网格总行数
     * @param N 网格总列数
     * @param X1 第一个点的行坐标
     * @param Y1 第一个点的列坐标
     * @param X2 第二个点的行坐标
     * @param Y2 第二个点的列坐标
     * @return 两点之间的曼哈顿距离
     */
    static int manhattanDist(int M, int N, int X1,
                             int Y1, int X2, int Y2) {
        // 使用 Math.abs 计算绝对值并求和
        int dist = Math.abs(X2 - X1) + Math.abs(Y2 - Y1);
        return dist;
    }

    // 主驱动代码
    public static void main(String args[]) 
    {
        // 定义网格环境大小
        int M = 5, N = 5;

        // 初始化第一个点和第二个点
        int X1 = 1, Y1 = 2;
        int X2 = 3, Y2 = 3;

        // 打印计算结果
        System.out.println("曼哈顿距离: " + 
            manhattanDist(M, N, X1, Y1, X2, Y2));
            
        // 让我们尝试一个更远的距离测试
        System.out.println("测试 (0,0) 到 (4,4) 的距离: " + 
            manhattanDist(5, 5, 0, 0, 4, 4)); // 预期输出 8
    }
}

3. Python3 实现

Python 的简洁性在这里体现得淋漓尽致。我们可以直接编写公式，或者利用 math 库。注意处理整数和浮点数的转换。

# Python3 代码实现：计算二维数组中两点间的曼哈顿距离
import math

def manhattanDist(M, N, X1, Y1, X2, Y2):
    """
    计算两点之间的曼哈顿距离。
    
    参数:
    M, N : int -- 网格的边界
    X1, Y1 : int -- 起点坐标
    X2, Y2 : int -- 终点坐标
    
    返回:
    int -- 曼哈顿距离
    """
    # math.fabs 返回浮点数绝对值，使用 int() 转换回整数
    # 也可以直接使用 Python 内置的 abs() 返回整数
    dist = abs(X2 - X1) + abs(Y2 - Y1)
    return dist

# --- 主驱动代码 ---
if __name__ == "__main__":
    # 定义网格尺寸
    M, N = 5, 5
    
    # 定义点坐标
    X1, Y1 = 1, 2
    X2, Y2 = 3, 3

    # 计算并打印
    print(f"坐标 ({X1},{Y1}) 和 ({X2},{Y2}) 的距离是: {manhattanDist(M, N, X1, Y1, X2, Y2)}")

    # 实际应用模拟：计算两点是否相邻
    # 在网格中，如果曼哈顿距离为1，则两点是直接邻居
    dist = manhattanDist(5, 5, 1, 1, 1, 2)
    if dist == 1:
        print("这两个点是直接邻居！")

4. C# 实现

C# 常用于 Unity 游戏开发或 .NET 后端。在游戏中，计算网格移动距离非常常见。

// C# 代码实现：计算二维数组中两点间的曼哈顿距离
using System;

class ManhattanCalculator
{
    // 计算曼哈顿距离的函数
    static int manhattanDist(int M, int N, int X1, int Y1,
                             int X2, int Y2)
    {
        // Math.Abs 用于计算绝对值
        int dist = Math.Abs(X2 - X1) + Math.Abs(Y2 - Y1);
        return dist;
    }

    // 主驱动代码
    public static void Main()
    {
        // 定义虚拟网格大小
        int M = 5, N = 5;

        // 第一个点
        int X1 = 1, Y1 = 2;

        // 第二个点
        int X2 = 3, Y2 = 3;

        // 输出结果到控制台
        Console.WriteLine("距离计算结果: {0}", 
            manhattanDist(M, N, X1, Y1, X2, Y2));
    }
}

5. JavaScript 实现

Web 开发中，如果我们在做前端 Canvas 游戏或者简单的页面布局计算，这个逻辑也是通用的。


    // JavaScript 代码实现：计算二维数组中两点间的曼哈顿距离

    /**
     * 计算曼哈顿距离的函数
     * @param {number} M - 网格高度
     * @param {number} N - 网格宽度
     * @param {number} X1 - 点1 行
     * @param {number} Y1 - 点1 列
     * @param {number} X2 - 点2 行
     * @param {number} Y2 - 点2 列
     * @returns {number} 距离
     */
    function manhattanDist(M, N, X1, Y1, X2, Y2) {
        // Math.abs 计算绝对值
        let dist = Math.abs(X2 - X1) + Math.abs(Y2 - Y1);
        return dist;
    }

    // 主逻辑
    // 定义二维数组的大小
    let M = 5, N = 5;

    // 定义点
    let X1 = 1, Y1 = 2;
    let X2 = 3, Y2 = 3;

    // 在文档中输出结果
    document.write("计算结果: " + manhattanDist(M, N, X1, Y1, X2, Y2));
    
    // 控制台调试输出
    console.log("调试信息: 距离为 " + manhattanDist(M, N, X1, Y1, X2, Y2));

实际应用场景与最佳实践

掌握了基础计算后，让我们看看在实际开发中哪里会用到它。

  • 游戏开发（寻路算法）：

在基于网格的游戏（如策略战棋 RPG）中，计算角色的移动范围通常使用曼哈顿距离。例如，如果角色的移动力是 5，那么所有曼哈顿距离小于等于 5 的格子都是可达的。

  • 芯片设计（VLSI）：

在设计集成电路时，导线通常只能水平或垂直布线。计算两个组件之间的布线长度就是典型的曼哈顿距离应用。

  • 出租车定价：

在某些不能直线穿行的城市环境中，计算理论距离有时也会参考这种几何度量。

最佳实践与常见错误

  • 索引混淆： 一定要分清行（Row/X）和列（Col/Y）。将它们代入公式时顺序颠倒不会影响结果（因为加法交换律），但逻辑上必须清晰。
  • 浮点数精度： 如果你的坐标是浮点数（例如 1.5, 2.3），曼哈顿距离仍然适用，但结果可能是浮点数。在使用整数数组的语言（如 Java/C++）时，要注意类型转换。
  • 边界检查： 虽然曼哈顿距离公式本身不需要边界，但在实际应用中，你应该确保给定的点 $(X1, Y1)$ 和 $(X2, Y2)$ 确实在 $M \times N$ 的数组范围内，否则可能会导致数组越界错误。

性能优化建议

虽然计算单个曼哈顿距离已经是 $O(1)$ 的操作，非常快，但在某些极端情况下（比如计算几百万个点对之间的距离），我们仍然可以考虑优化：

  • 避免函数调用开销： 在极度性能敏感的循环中（例如 C++ 游戏引擎的底层循环），如果编译器没有进行内联优化，直接在循环体内写 abs(x1-x2) + abs(y1-y2) 可能比调用一个函数更快。
  • 位运算优化： 对于整数，计算绝对值通常涉及分支判断。某些底层系统可能会使用位运算来消除分支预测失败的风险，但这通常由编译器的 abs 函数自动处理，开发者手动优化的空间较小且会降低可读性。

总结

通过这篇文章，我们不仅学习了如何计算曼哈顿距离，还理解了它背后的几何意义以及在现实世界编程中的具体应用。它是一个简单却极其强大的工具，是任何处理网格系统程序员的必修课。

无论你是在使用 C++ 构建高性能游戏引擎，还是用 Python 编写数据处理脚本，掌握这个 $O(1)$ 的算法都将使你的代码更加高效和专业。下次当你遇到网格距离问题时，别忘了使用这个公式：

$$ \text{距离} =

X1 – X2

+

Y1 – Y2

$$

希望这篇文章对你有所帮助！你可以尝试修改上面的代码，比如编写一个函数来列出网格中距离某点特定步数内的所有点，以此来加深练习。

关键要点总结：

  • 公式： $ X1 – X2

    +

    Y1 – Y2

    $。

  • 复杂度： 时间 $O(1)$，空间 $O(1)$。
  • 应用： 网格游戏寻路、集成电路布线、出租车距离估算。

祝你编程愉快！

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。如需转载，请注明文章出处豆丁博客和来源网址。https://shluqu.cn/33695.html
点赞
0.00 平均评分 (0% 分数) - 0 票

相关文章美国1G带宽/1T流量高速vps $17.99/年