Hỏi về trace back trong dynamic programming

[fomasudoi]

Cho một lưới ô vuông kích thước N*N. Từ 1 ô bất kỳ của lưới đc phép di chuyển sang ô có chung cạnh với nó. Cho trước số bước di chuyển (K), bắt đầu tính từ ô xuất phát (1,1), hãy tìm cách đi sao cho tổng các số trên các ô di chuyển qua là lớn nhất, mỗi ô của lưới có thể di chuyển qua bao nhiêu lần cũng được.

DỮ LIỆU: vào từ file NETSUM.INP có cấu trúc như sau:
- Dòng đầu chứa các số nguyên dương N,K ( 2 <= N <= 100, 1 <= K <= 10000).
- Dòng thứ i trong số N dòng tiếp theo chứa các số nguyên a là giá trị của các ô ( 0 < a <= 10000 )

KẾT QUẢ: Ghi ra file văn bản NETSUM.OUT:
- Dòng đầu tiên ghi tổng các số trên đường di chuyển đc
- K dòng tiếp theo mỗi dòng ghi tọa độ cảu 1 ô trên đường di chuyển ( bắt đầu từ (1,1) )

Ví dụ:

NETSUM.INP

5 7
1 1 1 1 1
1 1 3 1 9
1 1 6 1 1
1 1 3 1 1
1 1 1 1 1

NETSUM.OUT

21
1 1
2 1
2 2
2 3
3 3
2 3
3 3
Có bài toán như trên. Cách giải đệ quy thì dựa theo công thức:
f[i,j,k] = Max{f[i-1,j,k-1] , f[i+1,j,k-1] , f[i,j-1,k-1] , f[i,j+1,k-1]} + c[i,j]

Với
f[i,j,k]: lưu lại tổng lớn nhất trên hành trình khi đã đi được k phút và đang dừng tại ô (i,j)
c[i,j]: giá trị của ô (i,j)


Nhưng vẫn ko biết làm sao để chuyển về quy hoạch động và làm sao trace back để xuất tọa độ các ô đã đi qua. Ai có cao kiến xin giúp cái :(