Vượt Lưới Tốn Ít Năng Lượng
Points
28
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Cho một bảng lưới kích thước $R \times C$. Mỗi ô $(i, j)$ có một giá trị năng lượng tiêu tốn $A_{i, j} \ge 0$. Bạn xuất phát từ ô $(1, 1)$ và muốn đi đến ô $(R, C)$. Ở mỗi bước, bạn có thể di chuyển sang một trong 4 ô kề cạnh (trên, dưới, trái, phải). Tổng năng lượng của đường đi là tổng giá trị của tất cả các ô bạn đi qua (tính cả ô $(1, 1)$ và $(R, C)$). Hãy tìm tổng năng lượng nhỏ nhất có thể.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $R$ và $C$ ($1 \le R, C \le 500$).
- $R$ dòng tiếp theo, mỗi dòng chứa $C$ số nguyên $A_{i, j}$ ($0 \le A_{i, j} \le 10^9$).
Dữ liệu ra
- In ra tổng năng lượng nhỏ nhất để đi từ $(1, 1)$ đến $(R, C)$.
Ví dụ
| Input | Output |
|---|---|
| 3 3\n1 3 1\n1 5 1\n4 2 1 | 7 |
| 2 3\n5 1 2\n1 1 5 | 12 |
Giới hạn
- $1 \le R, C \le 500$
- $0 \le A_{i, j} \le 10^9$
Community Discussion