適切に考察を行うと、この問題は、壁 + グリッド外部からなる閉路のうち、 \(S\) と \(G\) を分断するものを数え上げる問題に言い換えることができます。

• ここでの「閉路」とは、\(8\) 方で隣接している壁同士を線で結んだ時にできるループのことを意味しています。このようなループの内部に \(S\) が、外部に \(G\) があれば \(S\) と \(G\) は互いに行き来することができません。

この「\(S\) と \(G\) を分断する」という条件がかなり厄介そうですが、これは次のような方法によって計算することができます。

まず、 \(SG\) 間のマス目からなるパスを 1 つ自由に取ります。以下の図の赤マスです。
次に赤いパスに上側から侵入できるようなマスからなる集合を考えます。以下の図の青マスです。 # は壁マスからなる閉路の一例です。

赤マスと青マスを使うと、閉路が \(S\) と \(G\) を分断する必要十分条件は実は次のように言い換えられます。

• 壁マスからなる閉路が青 - 赤間をまたいだ回数が奇数回である。

  • たとえば上の図では \(3\) 回またいでいます。

正当性を簡単に書きます。
壁からなる閉路について、壁のあるマスの中心同士を結んだ閉曲線とみなします。(下の図の点線です。)
次に、\(SG\) 間のマス目からなるパスの片側に沿って、\(S\) と \(G\) を線で結びます。(下の図の実線です。)

このとき閉曲線が \(S\) と \(G\) を分断する必要十分条件は、閉曲線と\(SG\) を結ぶ線が奇数回交差することになります。

• \(S\) を出発して線にそって \(G\) へ移動することを考えます。すると、閉曲線と\(SG\) を結ぶ線の交点を通るたびに閉曲線の内側/外側が入れ替わるので、\(S\) から \(G\) に辿り着くまでに 線同士が交差した回数の分だけ内外が入れ替わることになります。よって \(S\) と \(G\) が分断される、すなわち閉曲線の内側と外側(あるいはその逆)になるには、線同士が奇数回交差するのが必要十分です。

また、閉曲線が\(SG\) を結ぶ線と交差する回数は、閉路が赤マス-青マス間をまたぐ回数と一致します。よって、青マスと赤マスをまたいだ回数を数えれば \(S\) と \(G\) が分断されているか確認できることが示せました。

これが分かれば後は適切な言い換えにより最短路問題に帰着できます。 すなわち、ある赤く塗られたマス \((x,y)\) を選んで、

• \(d_{i,j,f} :=\) \((x,y)\) を始点として \(f \pmod 2\) 回 青-赤 間をまたいだ壁の立て方のうち \((i, j)\) までの距離が最短であるような立て方、およびその通り数。

を計算する問題を考えると、これは最短路問題そのままであり、求めたいものは \(d_{x,y,1}\) である、というのが大枠です。(細かい部分は省略します。また、グリッドの端の扱いが面倒なので注意して実装してください。)

計算量は \(N = \max(H, W)\) として \(\mathrm{O}(N^3)\) です。(制約が緩めなので \(\mathrm{O}(N^3 \log N)\) でも通ると思います。)

追記 : 3 ケースだけ WA が出る人は、以下のケースで正しい答えを出せているか確認してみるとよいでしょう。(答え: Yes, 6 1)

4 6
OG..OO
O.SO.O
OO..OO
OOOOOO