別解1

より実装、計算量ともに軽い解法を紹介します。

Sに隣接する.に、数字を順に \(1, 2, \ldots\) と振ってみましょう。 そして、陣取りゲームのように各マスから数字を広げていきます(これは幅優先探索などで可能です)。

このとき、異なる数字が隣り合ったならば、その数字を経由する閉路が存在することになります。

例として、サンプル1の時の状態を図示します。

222X
#2#1
3S11
3##1

Sから幅優先探索で数字を広げていくと、右上のマスXで1と2が衝突します。 この時、Sから1を経由してXに向かい、2を経由してSに戻る閉路が存在するということになります。

これらの実装は幅優先探索1回で行うことができます。 数字の書かれたマスに対して、周囲に.があれば自身の値に書き換え、自身と異なる数字が書かれているならばYesを出力する、という実装を行えばよいです。

もちろん、このアルゴリズムは探索の順序に影響されないため、深さ優先探索など異なる探索順を用いても結果は変わりません。

別解2

最大流を用いた解法を紹介します。

Sからある頂点Tへ \(N\) 本の異なるパスが存在することは、SからTへの最大流が \(N\) 以上であることと同値です。

従って、次のようなグラフを構築し、その最大流が \(2\) 以上か否かで答えを求めることができます。

• .と.が隣接する頂点間に流量 \(1\) の辺を貼る
• Sから隣接する.へ流量 \(1\) の辺を貼る

Tの候補はSに隣接する.のみ試せば良く、計算量は \(O(HW)\) です。

別解3

S及び隣接する.について、この2点間を結ぶ辺が橋(取り除くとグラフの連結成分数が増える辺)であると仮定しましょう。 この時、もしこの辺を含む閉路が存在するならば橋の性質に反するので、橋ならば閉路を持ちません。

逆に、橋でないことを仮定すると、この辺を通らないパスであって辺の両端を辿れるようなものが存在することになるので、閉路を持つことが分かります。

従って、Sに隣接する辺が橋かどうかを判定すればよく、LowLinkを用いることで \(O(HW)\) 時間で求めることができます。