[nhan_lqd]

Bổ sung thêm bài 2 Cấp tỉnh vòng 1 nè
Cho một mảng kích thước m*n chứa các số nguyên.Một ngưới xuất phát từ cột 1 đi dến cột n(bắt đầu từ ô nào của cột 1 cũng được).Quy tắc: từ ô A[i,j] chỉ có thể đi đến một trong các ô A[i,j+1], A[i+1,j+1], A[i-1,j+1].Nếu xuất phát từ ô ở dòng i=1 thì chỉ đuợc di chuyển sang ô A[i,j+1] hoặc ô A[i+1,j+1], nếu xuất phát từ ô ở dòng i=m thi chỉ được sang các ô A[i-1,j+1] hoặc ô A[i,j+1].Hãy tìm vị trí xuất phát và đường đi từ cột 1 sang cột n sao cho tổng các số ghi trên đường đi là lớn nhất.
Dữ liệu vào từ tệp bai2.inp:
dòng đầu ghi 2 so m,n lần lượt là số dòng và số cột.
các dòng tiếp theo ghi các số trên đường đi.
Dữ liệu ra ghi trong tep bai2.out:
n dòng đầu ghi tọa độ đường đi từ cột 1 đến cột n
dòng cuối ghi tổng lớn nhất tìm được.

VD:
inp
4 5
1 2 3 4 9
6 3 2 7 4
2 5 7 5 3
4 2 3 4 7
out
2 1
3 2
3 3
2 4
1 5
34