If the table has an odd number of rows, it is possible to route the coaster right to the end of the first row, then one cell down, left to the beginning of the second row, and one cell down again. By doing this, we can visit all cells in the first two rows and reduce the problem to a table without them. The reduced table again has an odd number of rows, so we can repeat the same procedure until we are left with only one row. Then we can simply move right to the end of the last row, in the process visiting all remaining cells.

Thus we have shown that with an odd number of rows it is possible to visit all cells, making that the optimal solution. A similar solution is possible in case we have an odd number of columns.

The most difficult case is a table with an even number of both rows and columns. We shall prove that it is impossible to visit all cells in that case.

Let us visualize the table as if the cells were coloured black or white, in a chessboard pattern. The upper left and lower right corners are coloured white. Every path between those two corners first enters a black cell, then white, black again, and so on until ending in a white cell. Thus, it enters an equal number of white and black cells. Since the path starts at the top left corner, which is white, in the beginning there are fewer unvisited white cells than there are black cells. It follows that not all cells can be visited.

If we leave a single black cell unvisited, we will be able to visit all remaining cells. On the other hand, if we leave a white cell unvisited, we will also be unable to visit two black cells, which is obviously not optimal.

We can select any black cell to leave unvisited. It is optimal to choose the one with the smallest amusement value. All that remains is finding a route that will visit all cells except for the chosen one.

Solution

We can visualize our algorithm as if two tokens were placed on the table, one in the upper left and another one in the lower right corner. We alternate moving one and the other until they meet in a cell. The two tokens' paths together form the solution.

If the chosen cell isn't in one of the first two rows, we can move the first token right to the end of the first row, then one cell down, left to the beginning of the second row, and one cell down again. Now we can ignore those two rows and continue.

Likewise, if the chosen cell isn't in the last two rows, we can backtrace using the lower token - left to the beginning of the last row, then one cell up, right to the end of the second-to-last row, and one cell up again. Now we can ignore the last two rows.

An analogous process can be used to visit the first or last two columns if they don't contain the chosen cell.

By repeating this procedure we will eventually reduce the table to only two rows and two columns. It is trivial to solve this case - we select the only possible route for the first token (right-down or down-right, the one not containing the chosen cell). Now the tokens have finally met in a single cell.

This can be implemented by keeping two direction arrays, one for each token. When the tokens meet, the first tokens' array contains the first part of the solution. We only need to reverse the order and direction of the second tokens' directions to obtain the rest.

Alternative solution

If the table contains only two rows, it is simple to find a solution. Otherwise, if the chosen cell isn't in the first two rows, they can be eliminated as described above.

On the other hand, if the chosen cell is in one of the first two rows, we can visit all cells of the first three rows except for the chosen one. Now we can ignore the first three rows, so the table is reduced to one with an odd number of rows, the solution of which is described above.

The details of this solution are left as an exercise for the reader.