题目描述补充

题目：最小路径和 II

给定一个 m x n 的网格，网格中的每个单元格都有一个整数值。同时，在网格中指定了一个起点和一个终点。除了起点和终点单元格之外，网格中的每个单元格都包含一个障碍物，即值为 -1 的单元格。从起点到终点，只能上下左右移动，且不能经过障碍物。求从起点到终点的最小路径和。

注意：

• 起点和终点的值始终为非负数。
• 你可以假设起点和终点不会是同一个单元格。
• 网格中的路径必须是连续的。

示例

输入：

grid = [
  [1,0,1],
  [0,-1,0],
  [1,0,1]
]
start = [0,0]
end = [2,2]

输出：

2

解释： 从起点 [0,0] 到终点 [2,2] 的路径可以是 (0,0) -> (0,1) -> (1,1) -> (2,2)，路径和为 1 + 0 + 1 = 2。

PHP 示例代码

function minPathSum($grid, $start, $end) {
    $m = count($grid);
    $n = count($grid[0]);
    
    // 创建一个与原始网格同样大小的 dp 数组，并初始化为 PHP_INT_MAX
    $dp = array_fill(0, $m, array_fill(0, $n, PHP_INT_MAX));
    
    // 设置起点的 dp 值为起点值
    $dp[$start[0]][$start[1]] = $grid[$start[0]][$start[1]];
    
    // 广度优先搜索
    $queue = new SplQueue();
    $queue->enqueue([$start[0], $start[1]]);
    $directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    
    while (!$queue->isEmpty()) {
        [$x, $y] = $queue->dequeue();
        
        for ($i = 0; $i < 4; $i++) {
            $newX = $x + $directions[$i][0];
            $newY = $y + $directions[$i][1];
            
            if ($newX >= 0 && $newX < $m && $newY >= 0 && $newY < $n && $grid[$newX][$newY] != -1 && $dp[$newX][$newY] == PHP_INT_MAX) {
                $dp[$newX][$newY] = $dp[$x][$y] + $grid[$newX][$newY];
                $queue->enqueue([$newX, $newY]);
            }
        }
    }
    
    return $dp[$end[0]][$end[1]];
}

// 测试示例
$grid = [
    [1,0,1],
    [0,-1,0],
    [1,0,1]
];
$start = [0,0];
$end = [2,2];
echo minPathSum($grid, $start, $end);  // 输出 2

Python 示例代码

from collections import deque

def minPathSum(grid, start, end):
    m, n = len(grid), len(grid[0])
    dp = [[float('inf')] * n for _ in range(m)]
    dp[start[0]][start[1]] = grid[start[0]][start[1]]
    queue = deque([(start[0], start[1])])
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    while queue:
        x, y = queue.popleft()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] != -1 and dp[nx][ny] == float('inf'):
                dp[nx][ny] = dp[x][y] + grid[nx][ny]
                queue.append((nx, ny))
    
    return dp[end[0]][end[1]]

# 测试示例
grid = [
    [1,0,1],
    [0,-1,0],
    [1,0,1]
]
start = [0,0]
end = [2,2]
print(minPathSum(grid, start, end))  # 输出 2

JavaScript 示例代码

function minPathSum(grid, start, end) {
    const m = grid.length;
    const n = grid[0].length;
    const dp = new Array(m).fill(null).map(() => new Array(n).fill(Infinity));
    dp[start[0]][start[1]] = grid[start[0]][start[1]];
    const queue = [[start[0], start[1]]];
    const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    
    while (queue.length > 0) {
        const [x, y] = queue.shift();
        for (const [dx, dy] of directions) {
            const nx = x + dx;
            const ny = y + dy;
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] !== -1 && dp[nx][ny] === Infinity) {
                dp[nx][ny] = dp[x][y] + grid[nx][ny];
                queue.push([nx, ny]);
            }
        }
    }
    
    return dp[end[0]][end[1]];
}

// 测试示例
const grid = [
    [1,0,1],
    [0,-1,0],
    [1,0,1]
];
const start = [0,0];
const end = [2,2];
console.log(minPathSum(grid, start, end));  // 输出 2

码小课网站中有更多相关内容分享给大家学习，涵盖了算法、数据结构、编程技巧等多个方面，欢迎访问学习。