\((G_i,G_j)\)を決め打ち、\((S_i,S_j)\)から\((G_i,G_j)\)まで移動して居座り続けることを考えます。\((G_i,G_j)\)まで移動する道中で楽しさ\(a\)のマスを通った時、最初から\((G_i,G_j)\)にいると仮定した時にに比べて\(A_{G_iG_j}-a\)だけ損をする（コストが掛かる）と考えることができます。\(a>A_{G_iG_j}\)となるマスについては、そのマスを通り過ぎていくのは明らかに損であるので通れないと考えてもよいです。こうすることで負のコストが無くなりダイクストラ法を適用することができます。最終的に得られる楽しさの最大値は\(A_{G_iG_j} \times K-(A_{G_iG_j}までのコストの最小値)\)です。ダイクストラをする中でマスを移動する回数が\(K\)を超えてしまう場合もありますが、そのような場合は\(K\)回を超えて移動する際のコストは余分であるので最適にはなり得ません。

すべてのマスについて\((G_i,G_j)\)と決め打った時に得られる楽しさの最大値を求め、さらにその最大値を取ることでこの問題を解くことができます。計算量は\(O(H^2W^2log(HW))\)です。

実装例(Python 752ms)