Problem D: 机器人竞走
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：38
Solved：23
Description
暑假里，社区举办了一场小小机器人走的竞赛，机器人从n*n的矩阵的最上一行任选一格出发，每一步只能移动到下一行的左下方、正下方及右下方的方格中。请你编程让小小机器人找出从最上面一行走到最下一行路径的最小和 。如下图所示，在4*4的矩阵中，小小机器人找到了一条最小和为 -55的路径 ( 12 -> -13 -> -32 -> -22 )。
Input
输入第一行为矩阵大小 n。以下 n行为矩阵数据，每行 n个整数，数字间空一格。
Output
输出一个路径最小和。
Sample Input Copy
4
-15 12 20 16
16 24 -13 -24
23 -32 -14 32
-22 11 -12 28
Sample Output Copy
-55
HINT
2=<n<=500, -1000=<矩阵格数字<=1000 。