当前位置： 面试刷题>> 最小路径和Ⅱ (经典算法题500道)
### 题目描述补充
**题目：最小路径和 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 示例代码
```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 示例代码
```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 示例代码
```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
```
码小课网站中有更多相关内容分享给大家学习，涵盖了算法、数据结构、编程技巧等多个方面，欢迎访问学习。