O - LRUD Maze Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

縦 N 行、横 M 列からなるグリッドが与えられます。 上から i 行目、左から j 列目のマスを (i,j) と表記します。 グリッドの各マスには L , R , U , D のいずれかの文字が書かれており、 今 (i,j) には S_{i,j} が書かれています。

このグリッド上では、今いるマスを (i,j) 、そこに書かれた文字を c として、以下の移動が可能です。

  • c = L かつ j\neq 1 のとき、マス (i,j-1) に移動する。
  • c = R かつ j\neq M のとき、マス (i,j+1) に移動する。
  • c = U かつ i\neq 1 のとき、マス (i-1,j) に移動する。
  • c = D かつ i\neq N のとき、マス (i+1,j) に移動する。

さて、あなたはこれから以下の操作をちょうど 1 回行います。

  • 整数 1 \le i \le N と 1 \le j \le M を選び、 (i,j) に書かれた文字を L , R , U , D のうち S_{i,j} とは異なる文字に書き換える。

この操作は全部で 3NM 種類あります。 それらのうち、「操作後のグリッド上で (1,1) から (N,M) へ到達可能なもの」の数を求めてください。

制約

  • 2 \le N,M \le 1000
  • N,M は整数
  • S_{i,j} は L , R , U , D のいずれか

入力

入力は以下の形式で標準入力から与えられます。

N M
S_{1,1} S_{1,2} \dots S_{1,M}
S_{2,1} S_{2,2} \dots S_{2,M}
\vdots
S_{N,1} S_{N,2} \dots S_{N,M}

出力

標準出力へ答えを一行で出力してください。

入力例 1

3 3
RDD
RLD
URU

出力例 1

3

以下の 3 種類が条件を満たします。

  • (1,2) を R に変える
  • (2,2) を R に変える
  • (2,2) を D に変える

入力例 2

3 3
UUU
RRR
DDD

出力例 2

0

答えが 0 になる場合もあります。

入力例 3

3 4
RDUU
LRDD
ULRU

出力例 3

22