The fastest solution is precalc (as usual :] ), but you can make your solution very fast without it. It is clear that there is some physical dependence in this problem - the line of optimal movement is some function (a parabola, I presume). So you can look for several nearest points with integer coordinates and use dp only for them. But it is much more difficult and unsafe, isn't it?

Not parabola, but cycloid! It's variational stuff :)!

What is cycloid's formula?