After 21 days and 56 submissions on IOI 2010 Maze, I finally broke the 100 point barrier and achieved a score of 100.081 / 100.

Methodology

It's just simulated annealing + a lot a lot of time.

The neighbour function to generate a new state was just randomly choosing one cell to change from '$$$\text{#}$$$' to '$$$\text{.}$$$' or from '$$$\text{.}$$$' to '$$$\text{#}$$$'. Remember to take care that there must be exactly one '$$$\text{.}$$$' at the edge of the maze at all times.

The energy function that we are optimizing is the question itself, which is the maximum shortest path.

The acceptance probability function is the classic exponential function based on the Boltzmann probability distribution.

Finally, the initial temperature used was $$$t_0 = 2.5$$$ with geometric temperature reduction $$$t' = t\cdot \alpha$$$ where $$$\alpha =$$$.

I did not do any optimisation for the energy function, So each iteration takes $$$O(RC)$$$, which is quite slow considering the extremely big $$$\alpha$$$ used. This is why I spent 21 days on this question as each run takes around 1 week to converge on the final answer.

Takeaways

For such a brain-dead solution, I actually learnt quite a lot of things about simulated annealing. Below is a short list of items to take note of while doing simulated annealing.

1.