Độ khó: Dễ (1/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Trên một lưới ô vuông hình chữ nhật ~M \times N~, tại mỗi ô ~(i; j)~ của lưới ta đặt một lượng thức ăn dành cho gián, tương ứng với số nguyên dương ~a_{ij}~. Từ ô hiện tại, gián có thể bò đến một trong 2 ô khác để ăn hết lượng thức ăn đặt ở ô đó là: ô kề cạnh bên phải và ô kề cạnh bên dưới. Ban đầu chú gián ở vị trí ô ~(1; 1)~ và giả thiết ô này không chứa thức ăn.

Yêu cầu: Hãy xác định lộ trình trong lưới của gián sao cho từ ô xuất phát đi đến ô cuối cùng ~(M; N)~, gián có thể ăn được một lượng thức ăn nhiều nhất.

Dữ liệu vào

• Dòng đầu ghi hai số nguyên dương ~M~ và ~N~ ~(0 \lt M, N \le 100)~.
• ~M~ dòng tiếp theo, mỗi dòng thứ ~i~ ghi ~N~ số nguyên dương ~a_{ij}~ ~(0 \le a_{ij} \le 100;\ i = 1..M;\ j = 1..N)~.

Kết quả

• Đưa ra màn hình một số nguyên, là lượng thức ăn lớn nhất mà gián có thể ăn được.

Sample Input 1

4 5
0 5 1 3 4
6 1 9 1 5
1 1 1 4 1
1 3 4 6 3

Sample Output 1

30

Sample Input 2

4 5
0 1 2 3 1
0 2 3 4 5
6 1 2 3 1
3 2 4 1 5

Sample Output 2

21

Nguồn: Bài tập QHĐ.