以下、 \((a,b)\) から \((c,d)\) に移動できることを \((a,b)\) から \((c,d)\) に有向辺があるとして考えます。

操作を行う前の状態で \((1, 1)\) から到達可能なマス全体の集合を \(S\) とします。

\((N, M) \in S\) かどうかで場合分けします。

\((N,M) \not \in S\) のとき

操作を行う前の状態で \((N, M)\) へ到達可能なマス全体の集合を \(T\) とします。

\(S\) のすべてのマス \(x\) に対して、周囲 \(4\) 近傍のうち入力で与えられた方向以外の \(3\) 方向のどれかであり、かつ行き先が \(T\) に含まれるような方向の数を数え上げると、それらの総和が答えになります。

\((N,M) \in S\) のとき

このとき \(S\) は \((1,1)\) から \((N, M)\) へのパスになっていることに注意します。

書き換えるマスで場合分けします。

• \((N, M)\) はどの文字でもよいため \(3\) 通り
• \(S\) に含まれていないマスもどの文字でもよいためそれぞれ \(3\) 通り
• \(S\) に含まれていて、 \((N, M)\) ではないマスは複雑なので詳しく説明します

操作を行う前の状態で、 \((1, 1)\) からいま見ているマスまでのパスに含まれるマスを利用せずに \((N, M)\) へ到達可能なマス全体の集合を \(T\) としたとき、 周囲 \(4\) 近傍のうち入力で与えられた方向以外の \(3\) 方向のどれかであり、かつ行き先が \(T\) に含まれるような方向の数

これは \((N, M)\) から \((1, 1)\) へとパスをたどる順番で数え上げながら \(T\) を更新していけばよいです。 （ \(T\) を \((N,M) \not \in S\) のときと同じように定義してしまうと、書き換えた結果ループができてしまったときにも数え上げてしまいます。）

以上の合計が答えになります。

計算量

\(S, T\) は BFS や DFS などで求めることができるため、計算量は \(O(NM)\) です。

クレジット

原案： Levixi

解法： Levixi

問題準備・解説： Jinapetto

レビュー： US_cube

テスター： DEGwer

校正： nu50218, ngtkana