Hành trình săn kho báu trên lưới
Points
28
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề 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$
Community Discussion