Kobushide

以下のように考えても、答えは変わりません。

• 向かう先のマスが壁であっても移動できる。ただし、移動先が壁である場合、体力消費が になる。

このようにすると、グリッド上の最短経路問題になります。ダイクストラ法を用いることで、 で解くことができますが。高速な言語でないと厳しいと思います。
今回は移動コストが 種類であるため、01BFSを用いることにより で計算できます。Pythonではこれでもやや厳しめですが、頑張ってください。