\(1\) のマスから幅優先探索を行う. ただし, 探索中にそのマスにすでに辿り着いていた場合は, そのマスに辿り着くまでの距離はすでに辿り着いていた場合より小さくなることはないので, その枝は打ち切る.