(10,0 ĐIỂM) - DI CHUYỂN TỪ TRÁI SANG PHẢI. CHO HÌNH CHỮ NHẬT...

Bài 2(10,0 điểm) - Di chuyển từ trái sang phải. Cho hình chữ nhật M x N ơ vuơng, mỗi ơ chứa một số nguyên. Cĩ thể di

chuyển từ một ơ sang ơ thuộc cột bên phải cùng dịng hoặc chênh lệch một dịng. Tìm cách di chuyển từ một ơ nào đĩ thuộc

cột 1 đến một ơ nào đĩ thuộc cột N sao cho tổng các số nguyên chứa trong các ơ đi qua là nhỏ nhất.

Dữ liệu vào lấy từ file văn bản “Dichuyen.inp” dịng đầu là 2 số nguyên dương M, N. M dịng tiếp theo mỗi dịng ghi N số

nguyên của hình chữ nhật.

Kết quả ghi ra file văn bản “Dichuyen.out” gồm 2 dịng:

- Dịng thứ nhất ghi tổng các số nguyên chứa trong các ơ đi qua.

- Dịng thứ hai ghi N số là chỉ số dịng của các ơ đi qua từ cột 1 đến cột N.

Ví dụ:

DICHUYEN.INP

DICHUYEN.OUT

2 3

8

5 2 3

2 1 2

4 3 2

I. Phần chương trình nguồn