网格中的最短路径
网格中的最短路径
题目
给定一个m行n列的网格，每个格子里都有一个非负整数表示该格子的权值。现在你需要从左上角走到右下角，每次只能向右或向下走一步。求出从左上角到右下角的最短路径和。
例如，给定下面的3x3网格：
[1, 3, 1],
[1, 5, 1],
[4, 2, 1]
从左上角走到右下角的最短路径为1->3->1->1->1，路径和为6。
BFS解法
public static int minPathSum(int[][] grid) {
int m = grid.length; // 行数
int n = grid[0].length; // 列数
int[][] dist = new int[m][n]; // dist[i][j]表示从左上角到(i,j)格子的最短路径和
for (int[] row : dist) {
Arrays.fill(row, Integer.MAX_VALUE); // 初始化为无穷大
}
dist[0][0] = grid[0][0]; // 左上角格子的最短路径和为它的权值
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{0, 0}); // 将左上角的格子加入队列中
int[][] dirs = {{0, 1}, {1, 0}}; // 右、下两个方向
while (!queue.isEmpty()) {
int[] curr = queue.poll(); // 取出队首元素
int r = curr[0]; // 当前格子的行号
int c = curr[1]; // 当前格子的列号
for (int[] dir : dirs) { // 枚举右、下两个方向
int nr = r + dir[0]; // 新格子的行号
int nc = c + dir[1]; // 新格子的列号
if (nr >= 0 && nr < m && nc >= 0 && nc < n && dist[nr][nc] > dist[r][c] + grid[nr][nc]) {
// 如果新格子可达且它的最短路径和可以通过当前格子更新
dist[nr][nc] = dist[r][c] + grid[nr][nc]; // 更新新格子的最短路径和
queue.offer(new int[]{nr, nc}); // 将新格子加入队列中
}
}
}
return dist[m - 1][n - 1]; // 返回右下角格子的最短路径和
}
function minPathSum(grid) {
var m = grid.length; // 行数
var n = grid[0].length; // 列数
var dist = new Array(m);
for (var i = 0; i < m; i++) {
dist[i] = new Array(n).fill(Number.MAX_VALUE); // 初始化为无穷大
}
dist[0][0] = grid[0][0]; // 左上角格子的最短路径和为它的权值
var queue = [];
queue.push([0, 0]); // 将左上角的格子加入队列中
var dirs = [[0, 1], [1, 0]]; // 右、下两个方向
while (queue.length > 0) {
var curr = queue.shift(); // 取出队首元素
var r = curr[0]; // 当前格子的行号
var c = curr[1]; // 当前格子的列号
for (var _i = 0, dirs_1 = dirs; _i < dirs_1.length; _i++) {
var dir = dirs_1[_i];
var nr = r + dir[0]; // 新格子的行号
var nc = c + dir[1]; // 新格子的列号
if (
nr >= 0 &&
nr < m &&
nc >= 0 &&
nc < n &&
dist[nr][nc] > dist[r][c] + grid[nr][nc]
) {
// 如果新格子可达且它的最短路径和可以通过当前格子更新
dist[nr][nc] = dist[r][c] + grid[nr][nc]; // 更新新格子的最短路径和
queue.push([nr, nc]); // 将新格子加入队列中
}
}
}
return dist[m - 1][n - 1]; // 返回右下角格子的最短路径和
}
from queue import Queue
def minPathSum(grid):
m = len(grid) # 行数
n = len(grid[0]) # 列数
dist = [[float('inf')] * n for _ in range(m)] # dist[i][j]表示从左上角到(i,j)格子的最短路径和
dist[0][0] = grid[0][0] # 左上角格子的最短路径和为它的权值
queue = Queue()
queue.put((0, 0)) # 将左上角的格子加入队列中
dirs = [[0, 1], [1, 0]] # 右、下两个方向
while not queue.empty():
r, c = queue.get() # 取出队首元素
for dir in dirs: # 枚举右、下两个方向
nr = r + dir[0] # 新格子的行号
nc = c + dir[1] # 新格子的列号
if 0 <= nr < m and 0 <= nc < n and dist[nr][nc] > dist[r][c] + grid[nr][nc]:
# 如果新格子可达且它的最短路径和可以通过当前格子更新
dist[nr][nc] = dist[r][c] + grid[nr][nc] # 更新新格子的最短路径和
queue.put((nr, nc)) # 将新格子加入队列中
return dist[m - 1][n - 1] # 返回右下角格子的最短路径和
package main
import (
"fmt"
"math"
)
func minPathSum(grid [][]int) int {
m := len(grid) // 行数
n := len(grid[0]) // 列数
dist := make([][]int, m)
for i := 0; i < m; i++ {
dist[i] = make([]int, n)
for j := 0; j < n; j++ {
dist[i][j] = math.MaxInt32 // 初始化为最大整数
}
}
dist[0][0] = grid[0][0] // 左上角格子的最短路径和为它的权值
queue := [][]int{{0, 0}} // 将左上角的格子加入队列中
dirs := [][]int{{0, 1}, {1, 0}} // 右、下两个方向
for len(queue) > 0 {
curr := queue[0] // 取出队首元素
queue = queue[1:] // 弹出队首元素
r := curr[0] // 当前格子的行号
c := curr[1] // 当前格子的列号
for _, dir := range dirs { // 枚举右、下两个方向
nr := r + dir[0] // 新格子的行号
nc := c + dir[1] // 新格子的列号
if nr >= 0 && nr < m && nc >= 0 && nc < n && dist[nr][nc] > dist[r][c]+grid[nr][nc] {
// 如果新格子可达且它的最短路径和可以通过当前格子更新
dist[nr][nc] = dist[r][c] + grid[nr][nc] // 更新新格子的最短路径和
queue = append(queue, []int{nr, nc}) // 将新格子加入队列中
}
}
}
return dist[m-1][n-1] // 返回右下角格子的最短路径和
}
func main() {
grid := [][]int{
{1, 3, 1},
{1, 5, 1},
{4, 2, 1},
}
result := minPathSum(grid)
fmt.Println(result)
}
其中，dist[i][j]表示从左上角到(i,j)格子的最短路径和。我们先将dist数组初始化为所有格子的最短路径和都是无穷大，然后将左上角的格子的最短路径和设为它的权值，加入到队列中。接下来，我们使用BFS的方式遍历所有可达的格子，对于每个格子，我们尝试更新它相邻格子的最短路径和。如果相邻格子的最短路径和发生了更新，我们就将这个相邻格子加入到队列中进行后续的处理。最后，dist[m-1][n-1]就是从左上角到右下角的最短路径和。