问题描述
把儿站在一个N x N的方阵中最左上角的格子里。他可以从一个格子走到它右边和下边的格子里。每一个格子都有一个伤害值。他想在受伤害最小的情况下走到方阵的最右下角。
输入数据
第一行输入一个正整数n。
以下n行描述该矩阵。矩阵中的数保证是不超过1000的正整数。
输出数据
输出最小伤害值。
样例输入
3
1 3 3
2 2 2
3 1 2
样例输出
8
数据规模
n<=1000
【参考程序】:
var n,i,j:longint;
a:array[1..1000,1..1000]of longint;
begin
//while not eof do
//begin
readln(n);
for i:=1 to n do
for j:=1 to n do
read(a[i,j]);
for i:=2 to n do a[i,1]:=a[i,1]+a[i-1,1];
for i:=2 to n do a[1,i]:=a[1,i]+a[1,i-1];
for i:=2 to n do
for j:=2 to n do
if a[i-1,j]<a[i,j-1]then
a[i,j]:=a[i,j]+a[i-1,j]
else a[i,j]:=a[i,j]+a[i,j-1];
writeln(a[n,n]);
//end;
end.