Points
38
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved