求20×20网格中经指定点的两点最短路径的PHP实现、公式或算法名称

嘿，这个问题其实可以用很直接的思路解决，结合切比雪夫距离和枚举预定义点的方式就行，我给你拆解清楚：

适用算法名称 #

因为允许沿单元格对角线移动，两点间的最短距离遵循切比雪夫距离规则。而要求路径必须经过至少一个预定义点，我们只需要枚举所有预定义点，计算「起点→预定义点→终点」的总距离，取其中的最小值即可——这是最直接高效的方法，毕竟20×20网格的预定义点数量最多也才400个，计算量完全没问题。

核心计算公式 #

首先需要把网格的字母数字坐标转换成数值坐标（方便差值计算）：

• 横向：A=0, B=1, ..., T=19（从0或1开始都可以，不影响最终差值结果）
• 纵向：1=0, 2=1, ..., 20=19

对于任意两点(x1, y1)和(x2, y2)，切比雪夫距离公式为：

distance = max( abs(x1 - x2), abs(y1 - y2) )

对于每个预定义点P(xp, yp)，总路径距离为：

total_distance = distance(起点, P) + distance(P, 终点)

我们只需要从所有预定义点对应的total_distance中选取最小值，就是符合要求的最短路径长度。

PHP代码示例 #

下面是完整的可运行代码，包含坐标转换、距离计算、最短路径求解的逻辑：

<?php

/**
 * 将网格坐标（如A1、T20）转换为数值坐标数组[x, y]
 * @param string $coord 网格坐标字符串
 * @return array [x, y]
 */
function convertGridCoordToNumeric(string $coord): array {
    // 提取横向字母和纵向数字
    preg_match('/^([A-T])([1-20])$/', strtoupper($coord), $matches);
    if (empty($matches)) {
        throw new InvalidArgumentException("Invalid grid coordinate format. Use like 'A1' or 'T20'.");
    }
    
    // 字母转数字：A=0, B=1...T=19
    $x = ord($matches[1]) - ord('A');
    // 纵向数字转索引：1=0, 2=1...20=19
    $y = (int)$matches[2] - 1;
    
    return [$x, $y];
}

/**
 * 计算两点间的切比雪夫距离
 * @param array $point1 [x1, y1]
 * @param array $point2 [x2, y2]
 * @return int
 */
function calculateChebyshevDistance(array $point1, array $point2): int {
    $xDiff = abs($point1[0] - $point2[0]);
    $yDiff = abs($point1[1] - $point2[1]);
    return max($xDiff, $yDiff);
}

/**
 * 找到必须经过至少一个预定义点的最短路径距离
 * @param string $startCoord 起点坐标（如"A1"）
 * @param string $endCoord 终点坐标（如"T20"）
 * @param array $requiredPoints 预定义点坐标数组（如["C5", "G10", "M15"]）
 * @return int
 */
function findShortestPathWithRequiredPoint(string $startCoord, string $endCoord, array $requiredPoints): int {
    // 转换起点、终点为数值坐标
    $start = convertGridCoordToNumeric($startCoord);
    $end = convertGridCoordToNumeric($endCoord);
    
    $minTotalDistance = PHP_INT_MAX;
    
    foreach ($requiredPoints as $pointCoord) {
        $point = convertGridCoordToNumeric($pointCoord);
        // 计算起点到当前预定义点的距离
        $distToPoint = calculateChebyshevDistance($start, $point);
        // 计算当前预定义点到终点的距离
        $distFromPointToEnd = calculateChebyshevDistance($point, $end);
        // 总距离
        $totalDist = $distToPoint + $distFromPointToEnd;
        
        // 更新最小距离
        if ($totalDist < $minTotalDistance) {
            $minTotalDistance = $totalDist;
        }
    }
    
    if ($minTotalDistance === PHP_INT_MAX) {
        throw new RuntimeException("No valid required points provided.");
    }
    
    return $minTotalDistance;
}

// 示例使用
try {
    $start = "A1";
    $end = "T20";
    $requiredPoints = ["C5", "G10", "M15", "S18"];
    
    $shortestDistance = findShortestPathWithRequiredPoint($start, $end, $requiredPoints);
    echo "最短路径距离为：{$shortestDistance} 步\n";
} catch (Exception $e) {
    echo "错误：{$e->getMessage()}\n";
}
?>

代码说明 #

1. convertGridCoordToNumeric：把用户熟悉的网格坐标（如A1）转换成程序易计算的数值坐标，方便后续差值运算。
2. calculateChebyshevDistance：实现切比雪夫距离的计算逻辑，这是对角线移动下的最短步数公式。
3. findShortestPathWithRequiredPoint：核心逻辑，枚举所有预定义点，计算两段路径的总长度，记录最小值。

额外说明 #

• 如果预定义点数量很大，这个枚举法依然高效，因为每个计算都是O(1)的，总时间复杂度是O(n)（n是预定义点数量）。
• 如果你需要输出具体的路径（而不只是距离），可以在计算每个预定义点的路径时，记录每一步的坐标，最后选择总距离最小的那条路径的节点序列——这只需要扩展路径生成的逻辑即可。

内容的提问来源于stack exchange，提问作者Jeremy Ben