C - Crystal Researcher

2 secs 1024 MB
uni_kakurenbo's icon uni_kakurenbo

問題文

HH マス,横 WW マスの H×WH \times W マスからなるグリッドで表される洞窟があり,その洞窟の周囲はすべて奈落に囲まれています.
水晶研究員の MojaMoja 君は,この洞窟内に埋蔵されている水晶を発見したいです.

MojaMoja 君は,はじめ洞窟の左上のマスにいて,洞窟の右上のマスが正面となるように立っていました.
次に,下記に示すような規則に従い洞窟内で NN 回の行動をしました.

  • F, L, R, T のみからなる長さ NN の文字列 SS について,k(1kN)k \scriptsize \hspace{0.3em} (1 \leq k \leq N) 番目の行動では,
    • SkS_kF ならば,正面へ 11 マスだけ移動する.
    • SkS_kL ならば,その場で左に 9090 度回転する.
    • SkS_kR ならば,その場で右に 9090 度回転する.
    • SkS_kT ならば,その場で 180180 度回転する.

ただし,文字列 SS の先頭の文字は S1S_1 であり,SkS_k は文字列 SSkk 番目の文字を指します.
また,正面とは「その時に向いている方向」を指します.

この行為によって MojaMoja 君は,はじめにいた左上のマスを含めた洞窟内のすべての通行可能なマスを探索することができました.
MojaMoja 君が移動しなかったマスはすべて通行不能なマスです.

しかし MojaMoja 君は,探索の最中には一切の水晶を発見することはできませんでした.

水晶は,「上下左右に隣接する 44 マスすべてが 通行不能なマス または 奈落 であるマス」に隠れて埋蔵されている可能性があります.
通行不能なマスのうち水晶が埋蔵されている可能性のあるマスの総数を求めてください.

制約

  • 1H,W24001 \leq H,W \leq 2400
  • 1N2×1061 \leq N \leq 2 \times 10^6
  • H,W,NH,W,N は整数である
  • SSF, L, R, T のみからなる長さ NN の文字列
  • MojaMoja 君が,k(1kN)k \scriptsize \hspace{0.3em} (1 \leq k \leq N) 番目の移動を行ったとき,以下が成り立つ
    • Sk=S_k = F ならば,移動後のマスは奈落でない

入力

入力は以下の形式で標準入力から与えられる.

HWNH \hspace{0.5em} W \hspace{0.5em} N
SS

出力

答えを出力せよ.

サンプル

入力例1
4 6 11
FRFFLFRFLFF
出力例1
8

洞窟は以下のような形をしています.

洞窟
$$$$$$$$   $ : 奈落
$..#@@@$   # : 通行不能なマス(水晶が埋蔵されている可能性のないもの)
$#.#@@@$   @ : 水晶が埋蔵されている可能性のあるマス
$#..##@$   . : 通行可能なマス
$@#...#$
$$$$$$$$

入力例2
10 10 118
FFFFFFFFFLTFFFFFFTFLFFFFFFLFFFFRRTRFTFFFFFTFFFFLTFRFRFLFRTFFFFRTFFFFFRFFLTFRFRTFFFLFRFLFFFLFFTFFFFFTFFFFFFRRFRFFRFFRFL
出力例2
12

入力例3
10 10 300
FFFFRFRRFLLFFFFFFFFFLFFFFFTFFFFFTFFFTFFTFFFFRRTLFFFRRFFLTFFFFFFFFFTLFFFFRFFFFFFFFFRFFFFFRFFLTFFFFFFFTFFFFFFFRFFTFFFFTFFFFFFTFFFFRTLFLLFFFLFFFFFFFFFRRFFFFFFFFFLTFFFFFFLTFFFLFRFFTFFFFFTFFFFFRTFFTLFFFFRFRFFFFFFFFFTFFFRRFFFLLFRFLFFFFFFFFRFFFFFFFTFFFFRTRFFFFFTFFFLTFFRTLFFLLFFRFFRFFTLFFTRTFFFRFFFRFFFTFFFF
出力例3
0

残念なことに,MojaMoja 君の努力は全くの無駄であったようです.

提出


Go (1.21)