Cho một bảng vuông kích thước N*N (với 2 < N < 100). Mỗi ô trong bảng ghi một số nguyên a (a< ). Một robot di chuyển từ ô [1,1] xuống ô [n,n], mỗi bước robot chỉ có thể di chuyển sang ô cạnh bên phải hoặc bên dưới so với ô nó đang đứng.
Yêu cầu: Tìm đường đi của robot sao cho tổng đường đi là ngắn nhất.
Dữ liệu vào: Cho trong tệp robot.inp
- Dòng đầu ghi giá trị số n.
- Dòng thứ i trong n dòng tiếp theo ghi n số trên dòng i của bảng theo thứ tự từ trái qua phải.
Dữ liệu ra: Ghi ra tệp robot.out một số nguyên là tổng đường đi ngắn nhất tìm được.
Ví dụ:
robot.inp robot.out (Giải thích: đường đi có tổng bé nhất:
( 1,1) => (2,1) => (2,2) => (2,3) => (3,3)
có tổng: 1 + 5 + 4 + 2 + 2 = 14)
3
1 8 5
5 4 2
1 25 2 14 (KHÔNG ĐỆ QUY :)) )
Loga
Sinh Học lớp 12
