Mê cung chi phí ô
Points
38
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Cho bảng số kích thước $R \times C$, ô ở hàng $i$ cột $j$ có chi phí đi vào là $A[i][j] \ge 0$. Xuất phát từ ô $(1, 1)$, mỗi bước bạn có thể đi sang một trong bốn ô kề cạnh (lên, xuống, trái, phải). Hãy tìm tổng chi phí nhỏ nhất để đi đến ô $(R, C)$ (tổng chi phí bao gồm cả $A[1][1]$ và $A[R][C]$).
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $R, 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
- Một số nguyên duy nhất là tổng chi phí nhỏ nhất.
Ví dụ
| Input | Output |
|---|---|
| 3 3 1 3 1 1 5 1 4 2 1 |
7 |
| 2 3 5 1 2 3 4 1 |
9 |
Giới hạn
- $1 \le R, C \le 500$
- $0 \le A[i][j] \le 10^9$
Community Discussion