Hành trình săn kho báu trên lưới

Arrays Buổi 04 — Mảng 2D & Chuỗi Buổi 08 — Contest Chặng 1
Points
28
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Một nhà thám hiểm xuất phát từ ô $(1, 1)$ muốn đi tới ô $(N, M)$ trên bản đồ lưới $N \times M$. Tại mỗi bước, anh chỉ có thể đi sang phải hoặc đi xuống dưới. Ô $(i, j)$ có giá trị $a_{ij}$ (số vàng thu được), riêng các ô có $a_{ij} = -1$ là vách đá không thể đi qua. Hãy tìm tổng lượng vàng lớn nhất có thể thu được, hoặc in -1 nếu không có đường đi.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N, M$. $N$ dòng tiếp theo, mỗi dòng chứa $M$ số nguyên $a_{ij}$.

Dữ liệu ra

Tổng vàng lớn nhất thu được, hoặc -1 nếu không đi tới $(N, M)$ được.

Ví dụ
Input Output
3 3
1 2 3
0 -1 4
5 6 7
19
2 2
1 -1
-1 2
-1
Giới hạn
  • $1 \le N, M \le 500$
  • $a_{ij} = -1$ hoặc $0 \le a_{ij} \le 10^6$
Draft saved