初手の発想

問題は木の直径を求めると言い換えることができます。
つまり、ある一点から最も遠い点を選び、選んだ点から最も遠い点までの距離を求めればよい。
したがって、単純に幅優先探索を二回実行すれば回答できるはず。

間違い

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

修正

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

入力を

3 3
###
##.
##.

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

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

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

教訓

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