Atcoder Beginner Contest 151 D – Maze Master WAからの脱却

初手の発想

木の直径を求めると言い換えることができるので、ある一点から最も遠い点を選び、選んだ点から最も遠い点までの距離を求めればよい。

したがって、単純に幅優先探索を二回実行すれば回答できるはず。

間違い

最初に提出したコードでは テストケースのsmall_01 のみが通らず、 1WAでした。

修正

1ケースのみ通らないので極端な例がいけないはず。

入力を

3 3
###
##.
##.

として最小ケースを試行すると、1となるはずが2となりました。
つまり、2回カウントしているか、同じマス目を2回踏む間違いをしています。

上の視点でコードを睨んで、探索済みのマス目の処理が、初回だけ抜けていることを発見しました。
下のようにコードを修正します。

修正したのは12行目、bfs 内でスタートのマスの座標をqueue に入れる際に、探索済みにする行を追加したことです。

これでAC。

教訓

bfs, dfs などのqueue 管理の際に、最初のマス目を探索済みとする処理を忘れないこと。

コメント

タイトルとURLをコピーしました