#4298. C++ L11 路径上数字的最小和

C++ L11 路径上数字的最小和

C++ L11 路径上数字的最小和(30分)

题目名称:路径上数字的最小和

题目描述:

给定一个整数方阵,在某一列从第一行到最后一行画一条路径,再将路径的两端分别连接左上角元素和右下角元素。请找出从左上角元素到右下角元素的所有路径上数字和的最小值。

例如,一个4*4的方阵为:

image

可以发现,在黄色路径上数字和的最小值为22。

image

输入:

第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.