#4298. C++ L11 路径上数字的最小和
C++ L11 路径上数字的最小和
C++ L11 路径上数字的最小和(30分)
题目名称:路径上数字的最小和
题目描述:
给定一个整数方阵,在某一列从第一行到最后一行画一条路径,再将路径的两端分别连接左上角元素和右下角元素。请找出从左上角元素到右下角元素的所有路径上数字和的最小值。
例如,一个4*4的方阵为:
可以发现,在黄色路径上数字和的最小值为22。
输入:
第1行是1个整数n,表示矩阵的行数和列数(2 <= n <= 20)。
接下来的n行为n * n的方阵,其中每行有n个用单个空格隔开的非负整数(0~9)。
输出:
输出1个个整数,表示矩阵从左上角元素到右下角元素的所有路径上数字和的最小值。
输入样例:
4
1 2 3 4
6 7 8 1
5 4 3 2
1 3 6 9
输出样例:
22
Limitation
1s, 1024KiB for each test case.