青木君がいない場合は多点スタートBFSにより答えを求めることができます。
青木君がいる場合、マスから可能な移動のうち、移動後のゴールまでの操作回数が最短になるものは塞がれてしまうので、最短から2番目のものが答えになります。よってBFSにおいてそのマスに2回目に訪れたときに最短距離を更新すればよいです。

BFSにおいて、各マスに到達した回数を記録し、2回目に到達した際に答えの更新とキューへの追加を行うことで実現できます。

実装例(Python)