ABC213 E Stronger Takahashi
次の3つに場合分けして辺を張り, できたグラフ上で最短経路問題を解くことでこの問題を解くことができる.
道のマスから道のマスへ
この場合, 塀を壊す必要はないのでコスト0の辺を張ればよい.
塀のマスから道のマスへ
すでに塀に到着しているということを考慮すると, 今いるマスは道のマスであるのでコスト0の辺を張ればよい.
全マス共通
高橋君がいるマスをAで表現すると, 高橋君のパンチにより次に*で示すマスにコスト1で到着できるので, そのような辺を張ればよい.
. * * * .
* * * * *
* * A * *
* * * * *
. * * * .