B - Uniformly Distributed Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

H 行 W 列のマス目があります。上から i 行目、左から j 列目のマスをマス (i, j) と呼ぶことにします。
マス目の状態を表す H 個の文字列 S_1, S_2, S_3, \dots, S_H が与えられます。マス (i, j) の状態は以下の通りです。

  • S_i の j 文字目が R ならば赤く塗られている
  • S_i の j 文字目が B ならば青く塗られている
  • S_i の j 文字目が . ならば色が塗られていない

色が塗られていないマスの個数を k とすると、そのようなマスそれぞれを赤と青のどちらかで塗る方法は 2^k 通りありますが、このうち以下の条件を満たすものの個数を求めてください。

  • マス (1, 1) からマス (H, W) に、右または下へ 1 マス移動することを繰り返して辿り着くとき、途中で通過するマス (マス (1, 1), (H, W) を含む) のうち赤に塗られたものの数が、通る経路によらず一定である

ただし、答えは非常に大きくなることがあるので、998244353 で割った余りを出力してください。

制約

  • 2 \le H \le 500
  • 2 \le W \le 500
  • S_i は R, B, . からなる長さ W の文字列

入力

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

H W
S_1
S_2
S_3
\hspace{3pt} \vdots
S_H

出力

答えを 998244353 で割った余りを出力せよ。

入力例 1

2 2
B.
.R

出力例 1

2

マス (1, 1) からマス (2, 2) に、右または下へ 1 マス移動することを繰り返して辿り着く方法は以下の 2 通りあります。

  • マス (1, 1) \rightarrow (1, 2) \rightarrow (2, 2)
  • マス (1, 1) \rightarrow (2, 1) \rightarrow (2, 2)

マス (1, 2) とマス (2, 1) を異なる色で塗った場合、上記の 2 通りの移動方法のどちらを選ぶかによって、通過する赤く塗られたマスの数が変わってしまうため条件を満たしません。
一方で、マス (1, 2) とマス (2, 1) を同じ色で塗った場合、通過する赤く塗られたマスの数は移動方法によって変わらないため、条件を満たします。
よって条件を満たす塗り方は 2 通りあります。

入力例 2

3 3
R.R
BBR
...

出力例 2

0

条件を満たす塗り方が存在しないかもしれません。

入力例 3

2 2
BB
BB

出力例 3

1

色が塗られていないマスが存在せず、現在のマス目は条件を満たすため、答えは 1 となります。

Score : 400 points

Problem Statement

We have a grid with H rows and W columns. Let (i, j) denote the square at the i-th row and j-th column.
You are given H strings S_1, S_2, S_3, \dots, S_H that describe the square, as follows:

  • if the j-th character of S_i is R, (i, j) is painted red;
  • if the j-th character of S_i is B, (i, j) is painted blue;
  • if the j-th character of S_i is ., (i, j) is unpainted.

Let k be the number of unpainted squares. Among the 2^k ways to paint each of those squares red or blue, how many satisfy the following condition?

  • The number of red squares visited while getting from (1, 1) to (H, W) by repeatedly moving one square right or down, including (1, 1) and (H, W), is always the same regardless of the path taken.

Since the count may be enormous, print it modulo 998244353.

Constraints

  • 2 \le H \le 500
  • 2 \le W \le 500
  • S_i is a string of length W consisting of R, B, and ..

Input

Input is given from Standard Input in the following format:

H W
S_1
S_2
S_3
\hspace{3pt} \vdots
S_H

Output

Print the count modulo 998244353.

Sample Input 1

2 2
B.
.R

Sample Output 1

2

There are two ways to get from (1, 1) to (2, 2) by repeatedly moving right or down, as follows:

  • (1, 1) \rightarrow (1, 2) \rightarrow (2, 2)
  • (1, 1) \rightarrow (2, 1) \rightarrow (2, 2)

If we paint (1, 2) and (2, 1) in different colors, the above two paths will contain different numbers of red squares, violating the condition.
On the other hand, if we paint (1, 2) and (2, 1) in the same color, the two paths will contain the same numbers of red squares, satisfying the condition.
Thus, there are two ways to satisfy the condition.

Sample Input 2

3 3
R.R
BBR
...

Sample Output 2

0

There may be no way to satisfy the condition.

Sample Input 3

2 2
BB
BB

Sample Output 3

1

There is no unpainted square, and the current grid satisfies the condition, so the answer is 1.