The problem description is as such:
"You are given a square grid of positive and negative numbers. You have to start at the top left corner of the grid and find a path to the bottom-right corner. In each step, you are only allowed to move one position to the right or one position down. As a special bonus, you are allowed at most one move that can be either to the left or up. Note that you are allowed to visit a position more than once as a result of this special move.
Your aim is to find such a path that has the maximum weight, where the weight of a path is the sum of all the numbers visited along the path."
12 -16 10 -12
-16 13 -14 7
7 -4 16 -15
-7 16 -9 8
This is what I have thought of till yet.
So now after spending an hour on this I have no idea what the solution could be. Any hints please?
P.S: Keshav, this was the ZCO paper you gave in 2008 right? Were you able to solve it back then? :P