It is still doable with the special case, but you need to add a third logical dimension to your DP, indexed by a Boolean variable. This new dimension distinguishes between the scores before the special move (when the index is false) and the scores after the special move (when the index is true). The other two dimensions remain the grid's rows and columns.
When you compute the best score for a cell at [r][c], you must compute two values:
- A value where the third index is
false. This result is computed based only on other values from the dimension where the index is false, looking at the cells to the left and up from [r][c]
- A value where the third index is
true. This result is computed based on values from both indexes: you consider the items to the left and up where the index is true, and also the items to the left, to the right, up, or down from [r][c].
The second set of values (index == true) must be calculated after the entire set of the first items has been computed. In other words, you solve the problem with no special move, and then use the table for that solution to build an expanded table for the solution that allows special moves.
