DT1 - DT2
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: duytoannguyenledh

Trên một lưới vuông MxN (0<=M,N<=100), được chia thành các ô vuông đơn vị,  người ta để ở mỗi ô một lượng thức ăn Aij. Một chú Kiến xuất phát từ ô (1,1) đi qua sân để đến dòng thứ M. Chú Kiến chỉ có thể đi qua một ô kề cạnh bên phải hoặc một ô bên dưới ô đang đứng, mỗi lần đi qua một ô, chú Kiến ăn một lượng thức ăn trong ô đó. Hãy chỉ ra đường đi mà chú Kiến khi đi qua có thể ăn một lượng thức ăn lớn nhất.

Dữ liệu vào:

Dòng đầu là 2 số M, N

M dòng tiếp theo là một lưới ô vuông đơn vị, mỗi ô là lượng thức ăn.

Dữ liệu ra:

Dòng thứ nhất là lượng thức ăn lớn nhất

Dòng tiếp theo là đường đi mà chú Kiến đi qua

Ví dụ

INP

OUT

3  5

45

7   3   8   1    5

8     14  1

6  15  19 1    1

 

(1,1)

 (2,1)

 (2,2)

(2,3)

(3,3)

 

Ví dụ

Back to Top