Hi All,

Please help in this interesting grid problem.

There is a grid of dimension N * M (1 <= N,M <=500). Each cell contains a number K (0 <= K <= 10^5). Currently we are at cell (1,1) and we need to go to cell (N,M).We pick each number that is present in the current cell as we proceed along the path. Transitions are as follows: From position (r,c) we can go to (r+1,c) or (r,c+1) or (r+1,c+1).

We need to print the cell positions of lexicographical largest path among all possible paths. example :

1 2 3

4 5 6

7 8 9
In above matrix path [(1,1),(2,2),(3,3)] is largest.

Thanks in advance ...