I am developing a snake-like game that involving solving the following problem:

Given an m*n 2D grid, some of the locations are one while other locations are zero. The snake starts at (0,0) and will head toward the destination (m-1,n-1). At each step, it can only go right or down. Once it reached (m-1,n-1), it need to go back to (0,0) and in each step it can only go left or up. What is the maximum points it can get with this round trip?

If it is only an one-way trip, this can be easily solved with dynamic programming: max_gain(i,j)=max(max_gain(i+1,j),max_gain(i,j+1))+loc[i][j]. However, in my problem, it is a round-trip and one the way back, we must exclude points that are already taken on the way towards the destination. The input size (m and n) are around 1K so it is not practical to brute force it.