最小の移動距離となる経路は、真っすぐ進んでから一度だけ曲がるような経路のうちのいずれかになります。そこで、曲がってからどれだけ進めば、その経路の場合の最小移動距離になるのかを考えます。
最初にまっすぐ進んだ経路上にあるマスと同じ行、列にいる敵はすでに倒したと考えることができます。例えば、最初に縦方向に進む場合は、曲がってから横方向に進むべき距離は、縦方向についてそれより先にいる敵の、最大横座標になります。
最初に縦方向に真っすぐ進むことを考えます。各y座標より下で、最大のx座標を持つ敵のx座標を記録した配列を作ります（これをMX[H]）とします。入力時に各y座標での最大x座標を求めておけば、MXはO(H)で求めることができます。