1 3 1
1 5 1
4 2 1

7

1 2 3
4 5 6

12

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

// 使用 Solution 类包装功能函数，符合 LeetCode 风格
class Solution {
public:
    // 求解最小路径和的函数
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();          // m 行
        int n = grid[0].size();       // n 列
        vector<vector<int>> dp(m, vector<int>(n, 0));  // 定义动态规划数组
        dp[0][0] = grid[0][0];        // 起点初始化

        // 初始化第一列
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        // 初始化第一行
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }
        // 动态规划状态转移
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[m-1][n-1];  // 返回终点的最小路径和
    }
};

int main() {
    vector<vector<int>> grid;  // 存放输入的网格
    string line;
    // 使用 getline 读取每一行输入，适应 ACM 模式
    while(getline(cin, line)){
        if(line.empty()) continue;
        stringstream ss(line);
        vector<int> row;
        int x;
        // 解析一行中的数字
        while(ss >> x){
            row.push_back(x);
        }
        if(!row.empty()){
            grid.push_back(row);
        }
    }
    if(grid.empty()) return 0;
    Solution sol;
    // 输出结果
    cout << sol.minPathSum(grid) << endl;
    return 0;
}

# 定义 Solution 类，符合 LeetCode 风格
class Solution:
    def minPathSum(self, grid: list) -> int:
        m = len(grid)      # m 行
        n = len(grid[0])   # n 列
        # 初始化动态规划数组 dp
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = grid[0][0]  # 起点初始化

        # 初始化第一列
        for i in range(1, m):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        # 初始化第一行
        for j in range(1, n):
            dp[0][j] = dp[0][j-1] + grid[0][j]
        # 状态转移
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        return dp[m-1][n-1]  # 返回终点的最小路径和

if __name__ == '__main__':
    import sys
    grid = []
    # 逐行读取输入数据
    for line in sys.stdin:
        if line.strip() == '':
            continue
        # 解析每行的数字
        row = list(map(int, line.split()))
        grid.append(row)
    if grid:
        sol = Solution()
        # 输出结果
        print(sol.minPathSum(grid))

import java.util.*;
import java.io.*;

public class Main {
    // 定义 Solution 类，符合 LeetCode 风格
    static class Solution {
        public int minPathSum(int[][] grid) {
            int m = grid.length;        // m 行
            int n = grid[0].length;     // n 列
            int[][] dp = new int[m][n]; // 定义动态规划数组 dp
            dp[0][0] = grid[0][0];      // 起点初始化

            // 初始化第一列
            for (int i = 1; i < m; i++) {
                dp[i][0] = dp[i-1][0] + grid[i][0];
            }
            // 初始化第一行
            for (int j = 1; j < n; j++) {
                dp[0][j] = dp[0][j-1] + grid[0][j];
            }
            // 状态转移
            for (int i = 1; i < m; i++){
                for (int j = 1; j < n; j++){
                    dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
                }
            }
            return dp[m-1][n-1];  // 返回终点的最小路径和
        }
    }
    public static void main(String[] args) throws IOException {
        // 使用 BufferedReader 读取输入
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        ArrayList<int[]> gridList = new ArrayList<>();
        // 逐行读取输入数据
        while((line = br.readLine()) != null && line.length() != 0){
            String[] parts = line.trim().split("\\s+");
            int[] row = new int[parts.length];
            // 解析每行中的数字
            for (int i = 0; i < parts.length; i++){
                row[i] = Integer.parseInt(parts[i]);
            }
            gridList.add(row);
        }
        if(gridList.size() == 0) return;
        int m = gridList.size();            // m 行
        int n = gridList.get(0).length;       // n 列
        int[][] grid = new int[m][n];
        // 构造二维数组
        for(int i = 0; i < m; i++){
            grid[i] = gridList.get(i);
        }
        Solution sol = new Solution();
        // 输出结果
        System.out.println(sol.minPathSum(grid));
    }
}