Bài 3: Kinh nghiệm (7 điểm)
Hai anh em An và Bình tham gia một trò chơi thám hiểm trên bảng số xTremeMaze. Bảng có kích thước N x M (N dòng và M cột). Các ô trong bảng được đánh số từ trái sang phải và từ trên xuống dưới.
Tại mỗi ô của bảng có ghi một số nguyên là số điểm kinh nghiệm mà người chơi sẽ nhận được khi đi vào ô này. Cần lưu ý là số điểm tại một số ô có thể là số âm; khi đó, điểm kinh nghiệm của người chơi sẽ bị giảm nếu đi vào ô này.
An và Bình bắt đầu tại ô trái trên, đánh số là (1, 1). Mỗi lượt, một người chỉ có thể di chuyển tới ô kề cạnh ngay phía dưới hoặc ô kề cạnh ngay bên phải và không được phép đi ra khỏi bản. Khi đi qua mỗi ô, người chơi nhận được số điểm kinh nghiệm bằng số nguyên ghi ở ô đó. Hành trì kết thức tại ô (N, M).
Mục tiêu của trò chơi này là giúp hai anh em đạt được tổng số điểm cao nhất có thể. Theo quy định, các ô mà An và Bình đi quan không được phép trùng nhau, ngoại trừ ô bắt đầu tại vị trí (1, 1) và ô kết thúc tại vị trí (N, M). Quy ước: giá trị điểm kinh nghiệm tại ô (1, 1) và ô (N, M) đều bằng 0.
Yêu cầu: Hãy viết chương trình tính tổng số điểm kinh nghiệm lớn nhất mà An và Bình đạt được.
Dữ liệu: Vào từ file văn bản BROTHERS.INP gồm:
- Dòng đầu tiên chứa hai số nguyên N và M (2 ≤ N, M ≤ 200), số dòng và số cột của bảng.
-
N dòng tiếp theo, mỗi dòng ghi M số nguyên là số điểm kinh nghiệm tại mỗi ô trên bảng. Điểm kinh nghiệm tại mỗi ô có giá trị tuyệt đối không vượt quá 100.
Kết quả: Ghi ra file văn bản BROTHERS.OUT duy nhất một số nguyên là tổng điểm lớn nhất mà An và Bình có thể đạt được.
Ví dụ:
| BROTHERS.INP |
BROTHERS.OUT |
3 3
0 2 3
4 5 6
7 8 0 |
32 |
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?