C++/Find the greatest sum with moving cursor
This is an interesting programming question that I would like your help to solve. Though the explanation might seem long, it's actually quite interesting once you go through the program. In fact the program's input and output is quite simple too; it requires only input to make a diagram and one number as the output. Cursor movements are not part of the program's input and output, as you will see.
The question is the following:
The above is a sample diagram a user can provide as a possible input. A cursor would start moving from the bottom left of the diagram to the bottom right. The cursor follows a traditional scroll game, which means that it can move only to the right, up, or down. The cursor moves one grid location at a time, always to an adjacent location with no obstacle. He cannot occupy any location which he previously occupied - if he moves up, he cannot move down until he moves right; if he moves down he cannot move up until he moves right.
Each . on the diagram is an empty location which the cursor can move in, if he has previously never occupied that location before. Each * is an obstacle that the cursor cannot move in. Each number represents certain points.
The program must calculate and then output the greatest points that the cursor can pick while following all the above mentioned rules. The diagram above is only an sample and can be changed. For example, for the above diagram, the program will output 27 since 27 is the maximum points the cursor can pick up while following all the rules to move from the bottom left to bottom right (try it point yourself!). A diagram can range from 2 x 2 to 100 x 100. The below diagram is the smallest diagram possible.
In this case the output would be 34.
I have trouble coming up with a way to find the right algorithm to determine how the cursor should be moved to ensure the greatest number of points can be obtained. If you could give me suggestions on how the calculation should be like that would be very much appreciated.
I think the most difficult part of this program, is the way you should find the possible paths. If you can do that, then you should select the best path, which is the path that visits all. Sometimes, you might not be able to visit all numbers (depening on the map). In that case, you should choose the best path (that visits the most large numbers).
I hope this helps. For someone helping you with the programming tasksm you may contact firstname.lastname@example.org