最小路径和:ACM 模式刷题
按标准输入读取测试数据,输出结果后可在 CodeACM 在线运行和提交。
题目描述
给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
输入格式
第一行输入 m 和 n,接下来 m 行输入网格。
输出格式
输出最小路径和。
数据范围
- 1 ≤ m,n ≤ 200
- 0 ≤ grid[i][j] ≤ 200
公开样例
样例 1
输入
3 3 1 3 1 1 5 1 4 2 1
输出
7
路径 1→3→1→1→1 的总和最小,为 7。
样例 2
输入
2 3 1 2 3 4 5 6
输出
12
最优路径为 1→2→3→6。
练习建议
先根据输入输出格式写出可运行程序,再用公开样例检查结果;遇到边界情况时,补充自测用例后提交。